delpho

Think 문제를 보고, 벽 위치를 큐에 다 넣고 isVisited[][][]를 통해 한번에 bfs 돌리는 방식으로 풀었다. 하지만, 메모리 초과가 났고, 조건을 다시 보니 이해가 갔다. 골드2 정도로 올라오니 BFS에 시간초과 혹은 메모리 초과가 걸리도록 조건을 주는거같다. https://settembre.tistory.com/298 를 참고하니 이해가 갔다. 생각보다 어려운 방식은 아니지만, 생각의 전환이 필요했다. 내 정답 코드 import java.util.*; import java.io.*; public class test { static int N, M, map[][], resultMap[][]; static boolean[][] isVisited; static Map spaceMap = ne..

Think 30분정도 고민했는데 방법이 생각이 안났다. 규칙성이 있지 않을까 하면서 BFS를 활용해서 구현하는 방법을 고민했지만… 안됐다 https://loosie.tistory.com/253 를 참고했다. 0을 기준으로 BFS하면서 완전탐색을 하는 방식이었다. 0이 상하좌우 움직일때의 모든 경우의 수를 탐색해야하는데, boolean[][] 배열로는 불가능? 비효율?적이기 때문에 HashMap을 사용하여 중복체크를 한다. 또한, input을 2차원배열로 저장하지 않고, String으로 관리한다. 탐색할때는 나머지연산, 나누기 연산을 활용해서 위치를 관리한다. 이렇게 새로운 풀이방식이 나때마다 어떻게 이런 생각을 할까 하면서 감탄하게 된다 ㅎ.ㅎ.. 내 정답 코드 import java.util.*; imp..

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..