백준 3197 백조의 호수

작성일 | In |

Problem : 백조의 호수

유형 : BFS

문제 설명

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다.
두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

예제 입력

1
2
3
4
5
6
7
8
9
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력

1
2

해결 전략

맵이 어마무시하게 크다. 1500 x 1500이다.
일반적인 BFS로 접근할시 1500 ^ 3 으로 TLE 가 발생한다.

백조 한마리를 최대한 움직인다. 이 백조는 A백조라고 하겠다.
그리고 만약 다른 백조(B백조)를 만나지 못했다면, 현재 얼음벽 바로 옆에 서있을 것이다.
A백조가 이미 지나온길은 절대 정답이 되지 못한다.
그렇다면 A백조는 지나온길을 다시 갈 필요가 없으므로, 다음 시작 위치를 이동을 막은 얼음 좌표부터 시작한다.

이를 위해서 큐를 4개를 사용했다.
좌표 저장을 위해 굳이 큐를 쓸 필요가 없다. 다음 진행 좌표를 담기 위해 큐를 사용하면 pop 작업이 추가되어 복잡도가 늘어난다..라고 생각했는데 별차이가 없다.
이전 코드의 가독성이 너무 나빠 05-06 기준 수정.

  1. 백조를 움직일 BFS를 위한 큐
  2. 다음에 얼음이 녹은 후 백조가 BFS를 시작할 위치를 담은 벡터
  3. 현재 물인 위치를 담은 큐
  4. 다음에 녹을 얼음의 위치를 담은 벡터

주의할 점

  • 맵이 1500 x 1500이다.
  • 백조가 위치하고 있는곳도 물 이라고 생각해야한다. 이거 때문에 맞왜틀함
  • 백조 두마리를 동시에 움직이는 풀이도 생각 해보았으나, 고려할 부분이 너무 많아서 포기했다.

풀이

A 백조의 위치와, 지도 정보를 입력 받아 처리한다.

  • A백조란, 첫번쨰로 찾는 백조를 뜻한다. 어느 백조를 먼저 찾는지는 중요치 않다.
    • A백조를 B백조를 만날때까지 움직여 나갈것이다.
    • B백조가 있는 위치도 물로 생각하고, 주위의 얼음을 녹여 나가야 한다.
  • 현재 물의 좌표들을 입력받는다.

백조를 움직인다.

  • A백조를 BFS를 통해 움직여본다.
  • 만약 B백조를 만나지 못했다면, 얼음을 녹이고 다시 시도해야한다.
  • 지나온길을 다시 갈필요가 없다.
    • 백조의 다음 시작위치를 막혀서 가지 못한 좌표부터 시작한다.

얼음을 녹인다.

  • 물에 맞닿은 얼음의 위치를 찾으면, 해당 얼음을 녹인다.
  • 과거 얼음이었으나, 물로 바뀐 좌표부터 시작한다.

코드

05-06 수정

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
#include<bits/stdc++.h>
#define MAX 1501
#define x first
#define y second
#define pp pair<int, int>

using namespace std;

int n, m;
char board[MAX][MAX];
bool swan_visit[MAX][MAX], water_visit[MAX][MAX];

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

queue<pp> swan_q, water_q;


bool Find_Other_Swan() {

    vector<pp> nxt_swan;
    while (!swan_q.empty()) {
        pp cur = swan_q.front();    swan_q.pop();

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (swan_visit[nx][ny]) continue;

            if (board[nx][ny] == 'L') return true;
  
            if (board[nx][ny] == 'X') {
                swan_visit[nx][ny] = true;
                nxt_swan.push_back({ nx, ny });
                continue;
            }
            swan_visit[nx][ny] = true;
            swan_q.push({ nx, ny });
        }
    }

    for (const pp &it : nxt_swan) {
        swan_q.push(it);
    }
    return false;
}

void Water_Bfs() {

    vector<pp> nxt_water;
    while (!water_q.empty()) {
        pp cur = water_q.front();    water_q.pop();

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m)continue;
            if (water_visit[nx][ny])continue;

            if (board[nx][ny] == 'X') {
                water_visit[nx][ny] = true;
                board[nx][ny] = '.';
                nxt_water.push_back({ nx, ny });
                continue;
            }
            water_visit[nx][ny] = true;
            water_q.push({ nx, ny });
        }
    }

    for (const pp& it : nxt_water) {
        water_q.push(it);
    }

}

int Solve() {
    int cnt = 0;
    while (1) {
        if (Find_Other_Swan()) return cnt;
        cnt++;
        Water_Bfs();
    }
    return -1;
}

bool is_first_swan = true;

void Input() {
    cin >> n >> m;
    string line;
    for (int i = 0; i < n; ++i) {
        cin >> line;
        for (int ii = 0; ii < m; ++ii) {
            board[i][ii] = line[ii];

            if (board[i][ii] == 'L') {
                if (is_first_swan) {
                    swan_visit[i][ii] = true;
                    swan_q.push({ i, ii });
                    is_first_swan = false;
                }
                else {
                    water_visit[i][ii] = true;
                    water_q.push({ i, ii });
                }
            }
            else if (board[i][ii] == '.') {
                water_visit[i][ii] = true;
                water_q.push({ i, ii });
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    cout << Solve();

    return 0;
}

피드백

시간 복잡도 계산하는 연습을 좀 더 해야겠다.
문제 잘 읽는것이 진~짜 중요하다.

맞은사람 랭크 10위안에 든건 처음이다. 짤림