Post

[BaekJoon] 3197번 - 백조의 호수 [Java][C++]

Posted
By FickleBoBo
9 min read
[BaekJoon] 3197번 - 백조의 호수 [Java][C++]

문제 링크

1. 문제 풀이


물과 닿은 얼음은 매일 녹을 때 며칠 후 두 백조가 만날 수 있는지 구하는 문제로 단순히 얼음을 녹이고 백조가 만날 수 있는지 찾는 방식을 반복하는 것으로는 시간 내에 해결할 수 없다. 호수의 각 얼음에 대해 해당 얼음이 며칠 뒤에 녹는지를 전부 구한 후 매개 변수 이분 탐색을 통해 두 백조가 만날 수 있는 날을 탐색하는 방식으로 해결했다.

먼저 각 얼음이 녹는 날을 모두 구해야 하는데 이를 위해 호수를 한번 순회하며 물과 맞닿은 얼음의 좌표를 큐에 담았다. 이후 해당 큐에 대해 주변 얼음을 탐색하며 거리를 저장하면 해당 2차원 배열이 해당 좌표의 얼음이 녹는 날을 저장한 배열이 된다.

이후 해당 배열의 최댓값을 구하면 두 백조는 $0$ 일에서 최댓값에 해당하는 일 사이에서는 반드시 만나게 되므로 이를 매개변수 이분 탐색을 통해 특정일 이내에 녹는 얼음은 지나갈 수 있다고 가정하고 BFS를 돌려서 두 백조가 만날 수 있는 최솟값을 구했다.

2. 코드


1. 풀이 [Java]

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

import java.io.*;
import java.util.*;

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] 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());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        char[][] map = new char[R][C];
        List<int[]> pos = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') pos.add(new int[]{i, j});
            }
        }

        boolean[][] visited = new boolean[R][C];
        int[][] mark = new int[R][C];
        Queue<int[]> ice = new ArrayDeque<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] != 'X' && !visited[i][j]) {
                    Queue<int[]> result = bfs(i, j, R, C, map, visited);
                    ice.addAll(result);
                }
            }
        }
        bfs(ice, R, C, map, visited, mark);

        int max = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                max = Math.max(max, mark[i][j]);
            }
        }

        System.out.println(lowerBound(pos, max, R, C, mark));
    }

    static Queue<int[]> bfs(int sr, int sc, int R, int C, char[][] map, boolean[][] visited) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        visited[sr][sc] = true;

        Queue<int[]> ice = new ArrayDeque<>();

        while (!q.isEmpty()) {
            int[] node = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (visited[nr][nc]) continue;
                if (map[nr][nc] == 'X') {
                    ice.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    continue;
                }

                q.offer(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }

        return ice;
    }

    static void bfs(Queue<int[]> q, int R, int C, char[][] map, boolean[][] visited, int[][] mark) {
        int dist = 1;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int[] node = q.poll();
                mark[node[0]][node[1]] = dist;

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];

                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                    if (map[nr][nc] != 'X' || visited[nr][nc]) continue;

                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }

            dist++;
        }
    }

    static int lowerBound(List<int[]> pos, int max, int R, int C, int[][] mark) {
        int left = 0;
        int right = max;

        while (left < right) {
            int mid = (left + right) / 2;

            if (!bfs(pos, mid, R, C, mark)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static boolean bfs(List<int[]> pos, int max, int R, int C, int[][] mark) {
        int sr = pos.get(0)[0];
        int sc = pos.get(0)[1];
        int er = pos.get(1)[0];
        int ec = pos.get(1)[1];

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        boolean[][] visited = new boolean[R][C];
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            int[] node = q.poll();
            if (node[0] == er && node[1] == ec) return true;

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (mark[nr][nc] > max || visited[nr][nc]) continue;

                q.offer(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }

        return false;
    }
}


2. 풀이 [C++]

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int n, m;
char grid[1500][1500];
bool visited[1500][1500];
int mark[1500][1500];
vector<pair<int, int>> pos;
queue<pair<int, int>> ice;

queue<pair<int, int>> bfs(int sr, int sc) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    visited[sr][sc] = true;

    queue<pair<int, int>> q2;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (visited[nr][nc]) continue;
            if (grid[nr][nc] == 'X') {
                q2.push({nr, nc});
                visited[nr][nc] = true;
                continue;
            }

            q.push({nr, nc});
            visited[nr][nc] = true;
        }
    }

    return q2;
}

void bfs() {
    int dist = 1;

    while (!ice.empty()) {
        int sz = ice.size();

        while (sz--) {
            auto [r, c] = ice.front();
            ice.pop();
            mark[r][c] = dist;

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (grid[nr][nc] != 'X' || visited[nr][nc]) continue;

                ice.push({nr, nc});
                visited[nr][nc] = true;
            }
        }

        dist++;
    }
}

bool bfs(int mx) {
    auto [sr, sc] = pos[0];
    auto [er, ec] = pos[1];

    queue<pair<int, int>> q;
    q.push({sr, sc});

    memset(visited, 0, sizeof(visited));
    visited[sr][sc] = true;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (r == er && c == ec) return true;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (mark[nr][nc] > mx || visited[nr][nc]) continue;

            q.push({nr, nc});
            visited[nr][nc] = true;
        }
    }

    return false;
}

int lower_bound_param(int mx) {
    int left = 0;
    int right = mx;

    while (left < right) {
        int mid = (left + right) / 2;

        if (!bfs(mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'L') pos.push_back({i, j});
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != 'X' && !visited[i][j]) {
                queue<pair<int, int>> res = bfs(i, j);
                while (!res.empty()) {
                    ice.push(res.front());
                    res.pop();
                }
            }
        }
    }
    bfs();

    int mx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mx = max(mx, mark[i][j]);
        }
    }

    cout << lower_bound_param(mx);
}
PS, BaekJoon
Graphs Shortest Path BFS Binary Search Parametric Search
This post is licensed under CC BY 4.0 by the author.