1. 문제
설명
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
2. 풀이
풀이 자체만 보면 백준 - 빙산보다 하위 호환의 문제입니다.
BFS로 백조가 서로 만나는지 검사- 못 만나면 물과 인접한 빙판 깨기
위 두 가지만 반복하면 어쨋든 답은 구할 수 있기 때문에
'높이'까지 신경써야 하는데 '빙산' 문제보다는 구현면에서는 쉽습니다.
하지만 이 문제는 고려할 점이 하나 더 있는데요, 바로 효율성입니다.
보통 백조가 만나는지 검사할 때마다 visit배열을 사용하고,
못 만나면 다시 초기화하며 풀이를 했었겠지만 이 문제에서는 그렇게하면 시간 초과가 납니다.
이 때는 queue 자료구조를 더 사용하면 시간을 줄일 수 있습니다.
queue<pair<int, int>> swan, nSwan, water;swan은 백조가 만나는지 탐색할 때 쓰는 큐nSwan은 백조가 서로 만나지 못할 때, 탐색 재개 위치를 저장하는 큐water은 물의 좌표를 저장하는 큐
위 3개의 큐를 이용하면 매번 visit배열을 초기화할 필요 없이 답을 구할 수 있습니다.
1. 백조가 만나는지 검사한 후, 빙산일 때 nSwan에 좌표를 넣기
while (!swan.empty()) {
int y = swan.front().first;
int x = swan.front().second;
swan.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (visit[ny][nx]) continue;
// 만났을 때
if (lake[ny][nx] == 'L') {
isMeet = 1;
break;
}
// 물일 때, 탐색 계속
else if (lake[ny][nx] == '.') {
swan.push({ ny, nx });
visit[ny][nx] = 1;
}
// 빙판일 때, 다음 좌표 후보로 넣기
else {
nSwan.push({ ny, nx });
visit[ny][nx] = 1;
}
}
if (isMeet) break;
}
// 백조가 탐색을 시작할 좌표 세팅
while (!nSwan.empty()) {
swan.push(nSwan.front());
nSwan.pop();
}저도 그림을 그리면서 안 사실인데
백조가 서로 만나는지 검사할 때 처음 백조 위치부터 시작하는 게 아니라,
빙판이라서 막혔던 부분부터 진행하면 됩니다.
그 전까진 어차피 동일하게 탐색할테고, 빙판이였던 부분은 다음 날 물에 의해 깨지기 때문입니다.
2. 물 주위의 빙판을 깨고, 빙판을 깬 좌표를 다시 넣어주기
int size = water.size();
while (size--) {
int y = water.front().first;
int x = water.front().second;
water.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (lake[ny][nx] != 'X') continue;
water.push({ ny, nx });
lake[ny][nx] = '.';
}
}이 때 하루에 대해서 빙판이 깨져야하기 때문에 size만큼만 진행합니다.
3. 전체 코드
#define MAX 1500
#include <iostream>
#include <queue>
using namespace std;
int R, C;
int swanCoord[2];
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
char lake[MAX][MAX];
int visit[MAX][MAX];
queue<pair<int, int>> swan, nSwan, water;
bool isOut(int y, int x) {
return y < 0 || y >= R || x < 0 || x >= C;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> lake[i][j];
if (lake[i][j] != 'X') water.push({ i, j });
if (lake[i][j] == 'L') {
swanCoord[0] = i;
swanCoord[1] = j;
}
}
}
swan.push({ swanCoord[0], swanCoord[1] });
visit[swanCoord[0]][swanCoord[1]] = 1;
int day = 0;
while (1) {
int isMeet = 0;
while (!swan.empty()) {
int y = swan.front().first;
int x = swan.front().second;
swan.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (visit[ny][nx]) continue;
// 만났을 때
if (lake[ny][nx] == 'L') {
isMeet = 1;
break;
}
// 물일 때, 탐색 계속
else if (lake[ny][nx] == '.') {
swan.push({ ny, nx });
visit[ny][nx] = 1;
}
// 빙판일 때, 다음 좌표 후보로 넣기
else {
nSwan.push({ ny, nx });
visit[ny][nx] = 1;
}
}
if (isMeet) break;
}
// 만났을 때
if (isMeet) break;
// 백조가 탐색을 시작할 좌표 세팅
while (!nSwan.empty()) {
swan.push(nSwan.front());
nSwan.pop();
}
day++;
// 물 주위의 빙판을 깨고, 빙판을 깬 좌표를 다시 넣어주기
int size = water.size();
while (size--) {
int y = water.front().first;
int x = water.front().second;
water.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (lake[ny][nx] != 'X') continue;
water.push({ ny, nx });
lake[ny][nx] = '.';
}
}
}
cout << day;
return 0;
}