티스토리 뷰
생각
Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q16236.java 아기 상어가 혼자서 먹이를 혼자 먹으러 돌아다닐 때, 최소로 이동한 거리를 구하여라. 아기 상어는 자신보다 큰 물고기는 지나가지 못한다. 먹이가 여러개일때는 최소 거리, 같은 거리에 먹이가 있을 때는 위쪽, 위쪽에 여러 먹이가 있을 경우는 왼쪽을 우선시 한다.
처음 생각
먹이를 찾아 그 먹이를 잡아 먹어야한다. Queue를 사용해서 BFS 탐색을 통해 현 아기 상어 위치에서 먹이를 찾아주어야겠다고 생각하였다.
다음 생각
4방향 탐색을 통해 먹이를 찾는 탐색을 한다. 여러 먹이가 발견되면 해당 탐색 회차에서의 모든 먹이를 비교해서 조건에 만족하는 먹이를 찾아주어야한다.
▶ 때문에 queue의 탐색을 계속적으로 하는것이 아닌 처음에 queue의 size를 받아 한 회차 씩 돌려주었다. BFS 탐색이기 때문에 같은 반복문에서 돌아가는 정보들은 같은 회차이다.
다다음 생각
위의 탐색에서 조건에 알맞은 먹이를 찾게되면, 1) 그 먹이를 먹고 2) 먹은 횟수와 몸 크기를 비교해 같다면 몸 크기를 늘려주고 다시 먹은 횟수를 초기화 시킨 후, 3) 아기 상어의 위치를 먹이의 위치로 옮겨주었다.
▶ 아기 상어에 관한 일을 다 해주었으면 다음 탐색을위한 준비를 해주어야한다. 1) 이번 탐색에서 들어있던 queue들은 이제 필요없으므로 queue를 비어주었다. 2) 방문 배열을 초기화 해주었다. 3) 이동한 아기 상어의 위치를 기준으로 현 상태들을 다시 queue에 넣어주었다.
방안
1) queue의 size를 통해 한 회차씩 따져주는 연속적인 BFS 탐색하기.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | package baekjoon.q10000; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q16236 { static int n,x,y; static int[][] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); arr = new int[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { arr[i][j] = sc.nextInt(); // 아기 상어 최초 위치 if(arr[i][j]==9) { x=i;y=j; } } } // 먹이 탐색할 때 중복 제거 visited = new boolean[n][n]; solve(); } // 최적의 먹이를 먹고 다시 먹이 탐색할 때 private static void init() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) visited[i][j] = false; } } static boolean[][] visited; static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}}; private static void solve() { Queue<Pair> queue = new LinkedList<>(); // 초기 크기 2 queue.add(new Pair(x,y,2,0,0)); visited[x][y] = true; // 걸린 시간 int result = 0; while(!queue.isEmpty()) { int eatX=99,eatY=99; // 먹이감 발견시 그 위치 int eat=0,big=0,cnt=0; // for문으로 한 cnt씩 봐주므로, t를 밖에서 사용하기 위해 int size = queue.size(); // 최소로 도달하면 거기서 부터 다시 탐색을 해야하기 때문에 // 같은 cnt씩 묶어서 봐준다. for(int j=0;j<size;j++) { Pair t = queue.poll(); for(int i=0;i<4;i++) { int tx = t.x+dir[i][0]; int ty = t.y+dir[i][1]; if(tx<0 || ty<0 || tx>=n || ty>=n) continue; if(visited[tx][ty]) continue; // 현 몸집부다 크면 못 지나감 if(arr[tx][ty]>t.big) continue; visited[tx][ty]=true; queue.add(new Pair(tx,ty,t.big,t.eat,t.cnt+1)); // 아기 상어보다 작은 먹이를 발견하면 if(arr[tx][ty]!=0&& arr[tx][ty]!=t.big) { // 조건에 따라서 위쪽 & 왼쪽이 우선권 if(tx<eatX) { eatY = ty; eatX = tx; eat = t.eat; big = t.big; cnt = t.cnt+1; }else if(tx==eatX) { if(ty<eatY) { eatY = ty; eatX = tx; eat = t.eat; big = t.big; cnt = t.cnt+1; } } } } } // eatX가 바뀌었다는것은 이번 cnt에서 먹을것이 있다는 뜻. if(eatX!=99) { eat++; // 아그작 먹자 // 크기 커지기 if(eat==big) { big++; eat=0; } // 현 먹이 먹은 곳으로 아기 상어 이동 arr[x][y] = 0; arr[eatX][eatY] = 9; result += cnt; // 거기까지의 탐색 거리 x = eatX; y = eatY; // 아기 상어 위치 이동 init(); // 재 탐색을 위한 방문 초기화 queue.clear(); // 탐색하던 것들은 필요 없으므로 제거 visited[eatX][eatY] = true; // 현 위치에서 아기상어 다시 탐색 queue.add(new Pair(eatX,eatY,big,eat,0)); } } System.out.println(result); } static class Pair{ int x,y,big,eat,cnt; Pair(int x,int y,int big,int eat,int cnt){ this.x = x; this.y = y; this.big = big; this.eat = eat; this.cnt = cnt; } } } |
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 2741번 N 찍기 (0) | 2018.11.05 |
---|---|
[백준] 13908번 비밀번호 (0) | 2018.10.29 |
[백준] 16235번 나무 재테크 (3) | 2018.10.26 |
[백준] 16234번 인구 이동 (0) | 2018.10.25 |
[백준] 14395번 4연산 (9) | 2018.10.25 |
- Total
- Today
- Yesterday