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

01 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 3197 : 백조의 호수(링크)

알고리즘

1. 완전탐색
2. BFS
3. 두개의 큐를 활용한 완전탐색

풀이

1. 최단거리 탐색 - BFS
2. 두가지 큐를 이용한 Leveling
3. 물이 녹는 함수, 백조가 만나는 함수 두 개를 순차적으로 구현한 후 백조가 만날때까지 Flood Fill 알고리즘 구현
   • 백조에 대한 BFS
     • 인접한 방향이 물인 경우 => 현재 queue에 push
     • 인접한 방향이 빙판인 경우 => 백조의 next queue에 push
     • 인접한 방향이 백조 => boolean 값 true로 리턴한 후 종료
   • 물에 대한 BFS
     • 인접한 방향이 빙판 => 물의 next queue에 push
4. Tip
   • 문제의 단순화 : 꼭 백조의 위치를 두개 다 저장할 필요는 없다

코드

// BOJ-3197 : 백조의 호수
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa

const int MAX = 1504;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };

int n, m, swanY, swanX, visited_water[MAX][MAX], visited_swan[MAX][MAX], day = 0;
int a[MAX][MAX];

queue<pair<int, int>> waterQ, water_tmpQ, swanQ, swan_tmpQ;

// 커스텀 함수 reference 활용
void Qclear(queue<pair<int, int>>& q)
{
	queue<pair<int, int>> empty;
	swap(q, empty);
	return;
}

void water_melting()
{
	while (waterQ.size())
	{
		pair<int, int> tmp = waterQ.front();
		waterQ.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = tmp.first + dy[i];
			int nx = tmp.second + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited_water[ny][nx]) continue;
			if (a[ny][nx] == 'X')
			{
				visited_water[ny][nx] = 1;
				a[ny][nx] = '.';
				water_tmpQ.push({ ny,nx });
			}
		}
	}
	return;
}

// 백조가 만나는지 확인하는 bool 값 리턴 함수
bool move_swan()
{
	while (swanQ.size())
	{
		pair<int, int> tmp = swanQ.front();
		swanQ.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = tmp.first + dy[i];
			int nx = tmp.second + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited_swan[ny][nx]) continue;
			visited_swan[ny][nx] = 1;
			if (a[ny][nx] == '.') swanQ.push({ ny, nx });
			else if (a[ny][nx] == 'X') swan_tmpQ.push({ ny, nx }); // swanQ 사이즈는 증가하지 않는다 (무한루프는 언젠가 종료됨)
			else if (a[ny][nx] == 'L') return true;
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			a[i][j] = str[j];
			// 문제의 단순화 - 백조의 위치를 두개를 꼭 저장할 필요가 없다
			if (str[j] == 'L')
			{
				swanY = i;
				swanX = j;
			}
			if (str[j] == '.' || str[j] == 'L') visited_water[i][j] = 1, waterQ.push({ i,j });
		}
	}

	swanQ.push({ swanY, swanX });
	visited_swan[swanY][swanX] = 1;

	while (true)
	{
		if (move_swan()) break;
		water_melting();
		waterQ = water_tmpQ;
		swanQ = swan_tmpQ;
		
        // Queue clear의 두가지 방법
		while (!water_tmpQ.empty()) water_tmpQ.pop(); // queue clear
		Qclear(swan_tmpQ);
		day++;
	}

	cout << day << '\n';

	return 0;
}

평가

• 일반적인 BFS와 중간 목표 지점에 도달함에 따라 Leveling을 시키는 구조를 짜기위한 알고리즘
• 두 개의 Queue를 활용하여 임시 지점을 저장해 둘 수 있고 queue의 한 size를 모두 돌았을 때 원래 queue에 미리 저장해 둔 tmp queue 값을 초기화하면서 탐색 이어 나가기