delpho

Think 4방탐색과 말 움직임을 구현하는건 어렵진 않았다. 다만 오른쪽 아래까지 가는 최단거리를 어떻게 구할지가 고민이었다. 처음에는 무조건 말 움직임으로 가는것이 최단거리이지 않을까 생각했다. 하지만, 탐색하려는 특정 정점까지의 최단거리는 무조건 말 움직임으로 갈때만이 최단 거리가 아니다. 1 5 5 00010 00010 00110 01110 00000 예를들어, 위의 인풋이 들어왔을떄, [5,2]까지 가는 최단거리는 3가지 방법이 있다. 4방탐색으로만 가기 (6번) / 말 움직임 먼저 간 후[2,1], 4방탐색으로 가기 (6번) / 4방탐색으로 먼저 간 후[2,1], 말 움직임으로 가기 (4번) 그렇기 때문에, 그리디로 풀수는 없고 완탐으로 풀어야된다는 생각을 했다. https://yabmoons...

Think 문제를 딱 봤을때 엄청 어려워보이진 않았다. 내부공기, 외부공기 구분 하는 것만 신경써주면 될거같았다. 가장자리는 무조건 치즈가 없으니, 0,0 BFS돌려서 외부공기로 넘버링하고, 치즈 탐색하면서 외부공기와 맞닿은 개수 체크한다음에, 녹은 치즈를 다시 외부공기로 넘버링 하는 방식으로 구현 녹은 치즈를 바로 외부공기로 넘버링하면, 다음 탐색하는 치즈가 접촉하는 외부 공기의 수가 +1 되어버리니, 일단은 0으로 변환한다음에 이후 외부공기로 수정 내 정답 코드 import java.util.*; import java.io.*; public class test { static int N, M, map[][],countCheeze; static boolean isVisited[][]; static Qu..

Think 문제를 처음 읽고나서 생각한 풀이는, 섬 가장자리 위치를 큐에 모두 저장하고, BFS를 한번에 돌리면 되겠다고 생각했다. 하지만, 가장자리 포인트들에서 동시에 BFS가 돌아가다보니, 거리가 상쇄가 되어버렸다. (거리가 4라면 2로 되어버림) 어떻게 풀지 계속 고민하다가 구글링을 했다. (https://todaycode.tistory.com/166) 풀이 방식은 이렇다. 각 섬들을 넘버링한다. (다른 섬의 경계에 도착했는지 체크하기 위함, 1로만 되어있는 섬 표식을 2,3,4로 표시 (2부터 넘버링하는게 더 편함)) 2중 for문을 돌면서 BFS를 시도한다. map[nextR][nextC] ≠ 0 이면, 섬 가장자리가 아니라는 의미이기 때문에 BFS를 진행하지 않는다. (다른 if문으로 인해 자..

Think 물고기를 어떤 자료구조로 관리할지, 상어기준으로 물고기와의 거리를 어떻게 계산할지, 먹는 우선순위를 어떻게 구분할지에 대해서 먼저 고민하고 시작했다. 물고기는 Fish라는 클래스를 만들고 LinkedList로 관리 / 상어와 물고기와의 거리는 BFS를 통해 계산 (한번 먹을때마다 다시 계산) / 우선순위는 Fish 클래스에 Comparable을 통해 정렬시키기 - 를 통해 구현했다 물고기 먹는 순서와 상어가 갇혔을때의 경우를 고려하지못해서 약간 정체됐지만, 그래도 풀었다. 188ms로 통과했길래 다른 사람은 얼마나 걸렸는지 봤는데 84ms로 통과한 사람이 있어서 풀이를 구경했다. 나는 상어가 물고기를 먹을때마다 물고기와의 거리를 계속 BFS를 통해 계산했는데, 이 사람은 BFS 한번만으로 풀어..