티스토리 뷰

알고리즘/백준

[백준] 16236번 아기 상어

머어하지 2018. 10. 27. 17:11

생각

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