BOJ - 3197번 백조의 호수(C++)

문제 출처: https://www.acmicpc.net/problem/3197

문제 난이도

Gold 1

문제 접근법

문제를 계속 bool check배열을 초기화하고 처음부터 호수 전체를 돌면, 시간 초과가 난다.
그래서 check 배열을 초기화시키지 않고 호수를 한 번만 탐색할 수 있도록 짜야한다.

1. 백조가 있는 곳도 물이다. 물이 있는 곳을 다 queue에 넣는다.
2. 물을 탐색해서 옆에 빙하가 있으면 물을 바꾸고 임시 queue에 넣는다.
3. 물로 바뀐 곳만 임시queue에 있으니 이 데이터를 다시 물이 있는 queue로 넣어준다.
   -> 이런 식으로 하면 처음부터 계속 돌지 않아도 된다. 물로 녹은 곳만 보면 된다.

백조 위치도 이와 비슷한 원리를 사용한다.

1. 백조 위치로 check하여 중복을 없앤다.
2. 백조가 물로 이동하다 빙판을 만나면 다음날에 녹으니, 임시 queue에 넣는다
3. 다음날, 빙판이 녹아있으니 다시 길을 찾는데 이때 다른 백조를 발견하면 break

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int R, C;
vector<string> arr;
bool isFind = false;
pair<int, int> swan;
queue<pair<int, int>> sq, wq, tmpSQ, tmpWQ;
int dy[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool ch[1501][1501];

void swanBFS() {
	while (!sq.empty()) {
		int x = sq.front().first;
		int y = sq.front().second;
		sq.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			if (nx < 0 || ny < 0 || nx >= R || ny >= C || ch[nx][ny]) continue;
			ch[nx][ny] = true;
			if (arr[nx][ny] == 'X') tmpSQ.push({ nx,ny });
			else if (arr[nx][ny] == '.') sq.push({ nx,ny });
			else if (arr[nx][ny] == 'L') {
				isFind = true;
				break;
			}
		}
	}
}

void waterBFS() {
	while (!wq.empty()) {
		int x = wq.front().first;
		int y = wq.front().second;
		wq.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
			if (arr[nx][ny] == 'X') {
				arr[nx][ny] = '.';
				tmpWQ.push({ nx,ny });
			}
		}
	}
}

int meetDay() {
	int day = 0;
	while (!isFind) {
		swanBFS();
		if (isFind) break;
		waterBFS();
		sq = tmpSQ;
		wq = tmpWQ;
		while (!tmpSQ.empty()) tmpSQ.pop();
		while (!tmpWQ.empty()) tmpWQ.pop();
		day++;
	}

	return day;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string str;
		cin >> str;
		arr.push_back(str);
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < arr[i].size(); j++) {
			if (arr[i][j] == 'L') {
				swan.first = i;
				swan.second = j;
			}
			if (arr[i][j] != 'X') {
				wq.push({ i,j });
			}
		}
	}
	ch[swan.first][swan.second] = true;
	sq.push(swan);
	cout << meetDay() << "\n";
	return 0;
}

피드백

시간초과가 나서 어떤 식으로 시간을 줄일지 감이 잡히지 않아 다른 사람 코드를 참고했다. 무조건 check배열을 초기화하는 것보다 이런 식으로 풀 수 있다는 걸 깨달았다.. 신기..

그리고 계속 틀려서 뭐때문이지? 백조가 있는 곳도 물로 여기고 queue에 넣었는데?! 라고 생각했으나 다시 보니 if/else if로 조건문에 걸려 못들어간것이였다..