문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
각 R줄 동안 C만큼의 문자열이 주어진다.
'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
풀이
| 3197 | 맞았습니다!! | 20656 | 336 | C++14 / 수정 | 3986 | 40초 전 |
1. BFS이나 그냥 BFS로는 시간초과가 발생한다.
2. 빙하가 녹는 날을 따로 저장해서 이분탐색을 해야한다.
이분 탐색을 하는 근거는 k번째 날에 두 백조가 만난다고 가정했을 때 k-1번째날에는 만날 가능성이 없기 때문이다.
3. 빙하가 녹는 날을 전처리 하기 위해 day라는 이차원 배열을 생성하고 meltingIce() 라는 함수를 호출했다.
4. meltingIce()에서는 바다가 있는 곳 (백조는 바다 위에 떠있기 때문에 백조가 있는 곳도 바다라고 가정한다) 을 큐에 넣고 인접한 빙하들을 aging한다.
5. 모든 빙하들을 전처리했으면 이분탐색을 해야한다.
left=0 right는 빙하가 녹는 날 중 최대로 정한다.
while(left <= right) 일 때 mid = 중간값으로 지정하고 mid 날일 때 두 백조가 만나는 지 확인한다.
6. 만약 백조가 만났다면 그 때의 날짜 (mid)를 최소값으로 지정하고 right = mid-1로 하여서 계속 탐색한다.
7. 만나지 못했다면 left = mid+1로 해서 만나는 날짜를 뒤로 미뤄준다.
8. 백조가 만나는 지 확인하는 함수는 check()로 두 백조 중 한 마리의 좌표를 큐에 넣은 후
mid를 limit로 두어 위에서 전처리한 day[][] <=limit 일 때 다른 한 백조를 만났다면 T 를 리턴하고
만나지 못했다면 다시 큐에 넣고 탐색한다.
큐가 모두 빌 때까지 못만났다면 false 리턴
9. BFS 선형탐색 (빙하녹이기 -> 백조가 만나는지 확인 -> 빙하녹이기 -> 백조 만나는지 확인 -> ...) 루틴은 BFS 호출이 많기 때문에
1500 * 1500 의 크기를 가진 맵에서는 시간초과가 발생한다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321
#define MAXX 1501
using namespace std;
int r, c;
char map[MAXX][MAXX];
int day[MAXX][MAXX];
typedef pair<int, int> pp;
pp swan1, swan2;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
queue<pp> ice;
bool visited[MAXX][MAXX];
bool check(int limit)
{
//두 백조가 만날 수 있는지 확인
queue<pp> q;
q.push(swan1);
memset(visited, 0, sizeof(visited));
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny])
continue;
if (day[nx][ny] <= limit)
{
visited[nx][ny] = true;
q.push(pp(nx, ny));
}
}
}
return false;
}
void meltingIce()
{
int label = 1;
{
int size = ice.size();
while (size--)
{
int x = ice.front().first;
int y = ice.front().second;
ice.pop();
bool flag = false;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny])
continue;
day[nx][ny] = label;
visited[nx][ny] = true;
}
}
label++;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> r >> c;
bool flag = false;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> map[i][j];
if (map[i][j] == 'L')
{
if (!flag)
{
flag = true;
swan1 = pp(i, j);
}
else
swan2 = pp(i, j);
visited[i][j] = true;
}
else if (map[i][j] == '.')
{
visited[i][j] = true;
}
}
}
meltingIce(); //빙하가 녹는 날짜를 미리 계산해서 days에 넣어둔다. (두 백조가 k번째 만나면 k-1번째는 당연히 만날 수 없다)
int left = 0, right = 0;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
right = right > day[i][j] ? right : day[i][j];
}
}
int ans = INF;
while (left <= right)
{
int mid = (left + right) / 2; //이분탐색하면서 날짜를 줄여간다.
if (check(mid))
{
ans = ans > mid ? mid : ans;
right = mid - 1; //만나더라도 계속 줄여나감 (최소값을 찾기 위해 )
}
else
left = mid + 1;
}
cout << ans << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
