티스토리 뷰

PS/Problem_Solving

[BOJ] 2573. 빙산(DFS, BFS).java

Aaron 2020. 11. 23. 23:17
반응형


#. Problem

https://www.acmicpc.net/problem/2573

* The copyright in this matter is in BOJ


 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it



#. Solve


치즈 문제와 유사한 문제다.


#. Code_v1


첫 번째 방법으로


먼저 BFS로 빙산을 녹여주고,

DFS로 빙산이 몇 덩어리로 분리되었지 count 해주었다.


이 해결 방법에서는 이전 map의 상태를 활용해야 해서 매시간 map을 copy 해주는 비용이들었다.

그래서 다른 해결 방법으로 풀어본 게 version 2이다.


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
118
119
120
121
122
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ2573 {
    
    static int N, M, cnt, map[][];
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Queue<Info> q = new LinkedList<>();
        map = new int[N][M];
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] > 0) q.add(new Info(i, j, map[i][j])); 
            }
        }
        
        System.out.println(process(q));
    }
    
    private static int process(Queue<Info> q) {
 
        int time = 0, size = 0;
        int[][] prevMap = new int[N][M];
        while(!q.isEmpty()) {
            
            ++time;
            size = q.size();
            // 이전 map 상태를 활용하기 위해 copy
            copy(prevMap, map);
            
            while(size-- > 0) {
                Info now = q.poll();
                int cnt = 0;
                
                // 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 녹는다
                for (int d = 0; d < 4; d++) {
                    int rr = now.r + dr[d];
                    int cc = now.c + dc[d];
                    if(rr < 0 || rr >= N || cc < 0 || cc >= M) continue;
                    if(prevMap[rr][cc] == 0) cnt++;
                }
                int nxth = now.h - cnt;
                // 빙산이 남았다면
                if(nxth > 0) {
                    q.add(new Info(now.r, now.c, nxth));
                    map[now.r][now.c] = nxth;
                } else {
                    // 빙산이 모두 녹았다면
                    map[now.r][now.c] = 0;
                }
            }
            
            // 빙산이 몇 덩어리로 분리되었는지
            cnt = 0;
            visited = new boolean[N][M];
            for (Info i : q) {
                if(visited[i.r][i.c]) continue;
                cntLump(i.r, i.c);
                cnt++;
            }
            // 빙산이 두 덩어리 이상으로 분리되었다면
            if( cnt >= 2) return time;
        }
        // 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않을 경우
        return 0;
    }
 
    private static void cntLump(int r, int c) {
        
        visited[r][c] = true;
        
        for (int d = 0; d < 4; d++) {
            int rr = r + dr[d];
            int cc = c + dc[d];
            // 범위를 벗어날 경우
            if(rr < 0 || rr >= N || cc < 0 || cc >= M) continue;
            // 이미 방문한 영역이거나 바다일 경우
            if(visited[rr][cc] || map[rr][cc] == 0) continue;
            
            cntLump(rr, cc);
        }
        
    }
 
    private static void copy(int[][] prevMap, int[][] map) {
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                prevMap[i][j] = map[i][j];
            }
        }
        
    }
 
    static class Info {
        int r, c, h;
 
        public Info(int r, int c, int h) {
            this.r = r;
            this.c = c;
            this.h = h;
        }
        
    }
}
 
cs



#. Code_v2


DFS로 빙산인 영역들을 돌면서

빙산 녹이기 + 몇 개의 덩어리로 분리되었는지 count


두 동작을 한 번에 처리해준다.


visit 상태이지만 빙산 높이가 0인 영역은 녹아서 빙산의 높이가 0이 된 상태이다.

이전에는 이 부분을 처리하려고 이전 map 상태를 활용했는데..


어차피 visit 상태인 영역은 다시 탐색하지 않으므로 version 1 처럼 이전 map 상태를 활용할 필요가 없었다.

(생각이 짧았다..)


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ2573_v2 {
    
    static int N, M, map[][];
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M]; // 빙산 높이 정보
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        System.out.println(process());
    }
    
    private static int process() {
 
        int time = 0, cnt = 0;
        while(true) {
 
            cnt = 0;
            visited = new boolean[N][M];
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    // 빙산이 있고 아직 방문하지 않은 영역일 경우
                    if(map[i][j] > 0 && !visited[i][j]) {
                        meltIce(i, j);
                        cnt++;
                    }
                }
            }
 
            // 빙산이 두 덩어리 이상으로 분리되었다면
            if( cnt >= 2) return time;
            // 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않을 경우
            else if(cnt == 0) return 0; 
            
            ++time;
        }
        
    }
 
    private static void meltIce(int r, int c) {
        
        visited[r][c] = true;
        // 4방 탐색
        for (int d = 0; d < 4; d++) {
            int rr = r + dr[d];
            int cc = c + dc[d];
            // 범위를 벗어나거나 이미 방문한 영역일 경우
            if(rr < 0 || rr >= N || cc < 0 || cc >= M || visited[rr][cc]) continue;
            // 바다일 경우
            if(map[rr][cc] == 0) {
                // 빙산이 녹는다...
                if(map[r][c] > 0) map[r][c]--;
            } else {
                meltIce(rr, cc);
            }
        }
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}
 
cs



반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[BOJ] 8983. 사냥꾼(이분탐색).java  (0) 2020.11.30
[BOJ] 13459. 구슬 탈출(시뮬레이션, BFS).java  (0) 2020.11.26
[BOJ] 15683. 감시(구현, 시뮬레이션).java  (0) 2020.11.22
[BOJ] 6593. 상범 빌딩(BFS).java  (0) 2020.11.19
[BOJ] 1759. 암호 만들기(조합).java  (0) 2020.11.19
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more