코테 기출 - 인프런/너비우선탐색(BFS) (6) 썸네일형 리스트형 숲속의 기사 ■ 풀이 board[][] 배열을 돌면서 영희와 기사 위치에서 산딸기 까지의 위치를 중첩시켜 dist[][] 배열에 저장한다. 너비우선탐색을 할 때마다 체크 배열을 새로 선언해서 사용한다.(이 문제의 경우 2번만 선언해서 사용하므로 문제가 없다.) 영희 -> 산딸기 -> 기사의 루트가 걸리는 시간은 영희 -> 산딸기 + 기사 -> 산딸기의 소요 시간과 같다. 탐색이 끝났다면 산딸기 위치중 dist 배열에 저장된 최소값을 찾으면 된다. 단, 0인 곳은 영희가 가지 못하는 곳이므로 제외한다. import java.util.*; class Main { public int solution(int[][] board) { int answer = Integer.MAX_VALUE; int[] dx = {-1, 0, 1.. 집을 짓자 ■ 풀이 1. dist[x][y]은 모든 빌딩에서 (x,y)좌표 지점까지 최소거리를 저장하는 2차원 배열이다. -> 이중for문으로 board[][]배열을 돌면서 빌딩 위치를 발견하면 너비우선탐색(BFS)을 시작해서 갈 수 있는 모든 지점의 최단거리를 누적 계산해 dist[][] 배열에 저장한다. -> 포문이 다 돌면 모든 빌딩으로부터의 최단거리가 dist[][]배열에 담기게 된다. 2. 빈 땅을 체크하는 emptyLand(정수형) 변수를 선언 -> 한 빌딩으로부터 최단거리를 구할 때 이미 방문한 땅은 체크하면 안되므로 방문한 빈 땅은 emptyLand - 1 값을 저장. -> 다음 빌딩으로부터 최단거리를 구할 때는 빈 땅을 emptyLand-1로 생각하고 반복 3. 현재 빌딩이 다른 빌딩이 갔던 빈 땅.. 미로의 최단거리 통로 ■ 풀이 각 좌표(x,y)에 도달하는 최단거리를 구하는 2차원 배열이 dist[x][y] 이고 다음 좌표를 (nx, ny)라고 했을 때 dist[nx][ny] = dist[x][y] + 1으로도 풀이 가능. import java.util.*; class Main { public int solution(int[][] board) { //북 동 남 서 int[] dx = {-1, 0, 1, 0}; int[] dy = {0, 1, 0, -1}; Queue Q = new LinkedList(); //각 지점에 도달하는 최단거리를 기록하는 2차원 배열 int[][] dist = new int[7][7]; Q.offer(new int[]{0, 0}); board[0][0] = 1; int L = 0; while (.. 송아지를 잡자 ■ 풀이 송아지가 이동하지 않고 현수만 이동해서 최소이동횟수를 구한다면 체크배열에 이미 방문했던 좌표를 체크하면 될것이다. 하지만 송아지가 이동하기 때문에 이미 방문했던 좌표도 다시 방문해야 한다. 그렇다면 체크를 해주지 않았을 때 다음과 같이 1 3 9 27 .... 3배수로 가짓수가 늘어나서 TimeLimit이 걸리게 되는데 어떤 규칙을 찾아야 할까? 바로 짝수 레벨과 홀수 레벨의 규칙성을 이용하는 것이다. 예를 들어 L = 4일때는 L = 2과 L = 0의 모든 가짓수를 포함하고 L=5일때는 L=3과 L=1의 모든 가짓수를 포함한다. (+1, -1 또는 -1, +1을 통해 2초만에 원래 자기 숫자로 돌아올 수 있음) 체크배열을 ch라고 했을 때 ch[L %2][다음 갈려는 지점] = 1이면 이전에 .. 집으로 이동 ■ 풀이 import java.util.*; class Main { public int solution(int[] pool, int a, int b, int home){ int answer = 0; //앞 뒤 점프 배열 int[] dx = {a, -b}; //방문 좌표 체크 배열 int[] ch = new int[10001]; //웅덩이 체크 for (int x : pool) ch[x] = 1; //이전 점프에서 뒤로 점프했는지 확인 boolean backJump = false; Queue Q = new LinkedList(); Q.offer(0); ch[0] = 1; int L = 0; while (!Q.isEmpty()) { int len = Q.size(); for (int i = 0; i < le.. 타일 점프 ■ 풀이 평범한 BFS 문제 import java.util.*; class Main { public int solution(int[] nums){ int n = nums.length; //방문한 좌표(인덱스번호) 체크 배열 int[] ch = new int[n]; QueueQ = new LinkedList(); //집 좌표(인덱스 번호) Q에 넣고 체크 Q.offer(0); ch[0] = 1; //최소 점프 횟수 int L = 0; while (!Q.isEmpty()) { int len = Q.size(); for (int i = 0; i < len; i++) { //현재 좌표 x int x = Q.poll(); for (int j = 1; j 이전 1 다음
