반응형

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

 

3197번: 백조의 호수

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 현재 호수의 상태를 저장할 queue<pair<int, int>> water, 다음 호수의 상태를 저장할 queue<pair<int, int>> tmpW, 현재 백조의 위치를 저장할 queue<pair<int, int>> swan, 마지막으로 다음 백조의 위치를 저장할 queue<pair<int, int>> tmpS를 선언합니다.

 

2. 호수를 입력받으면서 얼음이 아닌 좌표를 water에 push 하고, 백조 한 마리의 위치를 swan에 push 합니다.

 

3. 먼저 백조가 만날 수 있는지 bfs를 통해 움직이고, 벽에 마주칠 때마다 다음에 갈 수 있는 위치이므로 tmpS에 push 하고, 백조를 만난다면 Find 변수를 true로 갱신합니다.

 

4. 빙하가 녹으면서 현재 물에 맞닿아 있다면 tmpW에 push 해줍니다.

 

5. Find 변수가 true라면 ans를 출력해 주고, 그렇지 않다면 water = tmpW, swan = tmpS로 갱신해 주고, ans++를 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int R, C;
int r, c;
char arr[1500][1501];
int visited[1500][1500];
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
queue<pair<int, int>> swan, water, tmpW, tmpS;
bool Find = false;
 
void BFSwater()
{
    while (!water.empty()) {
        const int r = water.front().first;
        const int c = water.front().second;
        water.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C) {
                if (arr[rr][cc] == 'X') {
                    tmpW.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
            }
        }
    }
}
 
void BFSswan()
{
    while (!swan.empty() && Find == false) {
        const int r = swan.front().first;
        const int c = swan.front().second;
        swan.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C && visited[rr][cc] == 0) {
                visited[rr][cc] = 1;
                if (arr[rr][cc] == '.') {
                    swan.push({ rr,cc });
                }
                else if (arr[rr][cc] == 'X') {
                    tmpS.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
                else if (arr[rr][cc] == 'L') {
                    Find = true;
                    break;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
        for (int j = 0; j < C; j++) {
            if (arr[i][j] != 'X') {
                water.push({ i,j });
            }
            if (arr[i][j] == 'L') {
                r = i;
                c = j;
            }
        }
    }
 
    swan.push({ r,c });
    visited[r][c] = 1;
 
    int ans = 0;
 
    while (1) {
        BFSswan();
        if (Find == true) {
            cout << ans;
            return 0;
        }
        BFSwater();
        ans++;
 
        water = tmpW;
        swan = tmpS;
 
        tmpW = queue<pair<int, int>>();
        tmpS = queue<pair<int, int>>();
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21

+ Recent posts

티스토리툴바