[백준] 3197-백조의 호수(C++)

문제링크: https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

접근방식

 

1. 간만에 어려웠던 문제... 동작 자체는 쉽지만 시간초과, 메모리 초과때문에 삽질을 너무 많이했슴니다

2. 일반적인 얼음 녹이기, bfs를 사용하게 되며 매번 1500X1500짜리 필드를 탐색해주어야 하기때문에

O(1500*1500*cnt)로 당연히 시간 초과...

3. 이미 탐색한 영역은 넘어가고 새로운 영역만 bfs를 통해서 탐색할 수 있도록 구현하는 것이 핵심

 

문제풀이 

 

1. 백조하나를 기준으로 bfs를 진행함. 이때 다음번에 녹을 얼음을 임시큐에 저장해두었다가 bfs에서 사용하는 큐에 저장한다.

이렇게 행동함으로서 매번 bfs에는 새로 녹은 지점에만 탐색을 할 수 있도록 만드는 것이다. 

2. bfs이후에는 얼음을 녹이는 작업을 진행함. 기존 물좌표들은 pop으로 큐에서 빼고 얼음에서 물로 변한 위치들만 다시 큐로 넣어주는 방식이다 

 

 

아래는 정답코드!

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

typedef struct a {
	int y, x;
}dir;

dir ar[4] = { {1,0},{0,1},{-1,0},{0,-1} };

int r, c;
string arr[1500]; // 0 base
vector <dir> swan; // swan
queue <dir> vec; //water

queue <dir> q;
bool visited[1500][1500] = { 0, };


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> arr[i];
		for (int j = 0; j < c; j++) {
			if (arr[i][j] == 'L') {
				arr[i][j] = '.';
				swan.push_back({ i, j });
			}
			if (arr[i][j] == '.')
				vec.push({ i,j });
		}
	}

	q.push({ swan[0].y,swan[0].x });
	visited[swan[0].y][swan[0].x] = 1;

	for (int cnt = 0;; cnt++) {
		queue <dir> nq; //다음 단계 큐에 포함되는 값 

		bool flag = 0;
		while (!q.empty()) {
			int y = q.front().y;
			int x = q.front().x;
			q.pop();

			if (y == swan[1].y && x == swan[1].x) {
				flag = 1;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = y + ar[i].y;
				int nx = x + ar[i].x;
				if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx])
					continue;

				visited[ny][nx] = 1;
				if (arr[ny][nx] == 'X')
					nq.push({ ny,nx });
				else if (arr[ny][nx] == '.') {
					q.push({ ny , nx });
				}
			}
		}


		if (flag) {
			cout << cnt << endl;
			return 0;
		}

		q = nq;

		int ws = vec.size();
		while (ws--) {

			int y = vec.front().y;
			int x = vec.front().x;
			vec.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + ar[i].y;
				int nx = x + ar[i].x;

				if (ny < 0 || ny >= r || nx < 0 || nx >= c )
					continue;
				if (arr[ny][nx] == 'X') {
					arr[ny][nx] = '.';
					vec.push({ ny,nx });
				}
			}



		}


	}

	return 0;
}