[백준][bfs] 3197 백조의 호수 c++ 구현

목차

https://www.acmicpc.net/problem/3197

문제

첫 플레 문제

 

문제 구현 방향 

두개의 큐를 이용해서 구현했고 두번의 bfs를 차례로 실행하여 탐색하는 방식으로 진행했다.

 

물의 녹음 -> 백조의 이동

이것을 풀기 전에 아래 문제를 먼저 풀어보면 감이 잡힌다.(매우 유사하게 풀 수 있다)

https://be-senior-developer.tistory.com/123

[백준][bfs] 14497 주난의 난 (두개의 큐를 이용한 bfs) c++ 추가 구현

 

 

문제 풀이 시 주의점 

백조도 물로 취급해야 한다.

따라서 아래 반례가 존재한다.

1 7
LXX.XXL

//답은 1

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include<cstring>
using namespace std;

char board[1500][1500] = { '.' };
int visitwater[1500][1500] = { 0 };
int visitswan[1500][1500] = { 0 };
int R, C;
int m = 0;
int startX, startY, endX, endY;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int day = 0;

queue<pair<int, int>> waterq;  //물 녹음 큐
queue<pair<int, int>> swanq;   //백조 이동 큐

void watermelt() {
	while (1) {
		day++;
		queue<pair<int, int>> tmp;
        //물의 녹음
		while (!waterq.empty()) {
			
			int x = waterq.front().first;
			int y = waterq.front().second;
			waterq.pop();
		
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)
					continue;
				if (visitwater[ny][nx])
					continue;
                //x일 경우 따로 tmp에 저장해 놓는다.
				if (board[ny][nx] == 'X') {
					tmp.push({ nx, ny });  
					visitwater[ny][nx] = visitwater[y][x] + 1;
					board[ny][nx] = '.';
				}
			}
		}
		waterq = tmp;
        //tmp 초기화
		while (!tmp.empty()) {
			tmp.pop();
		}
		//백조의 이동
		while (!swanq.empty()) {
			int x = swanq.front().first;
			int y = swanq.front().second;
			swanq.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)
					continue;
				if (visitswan[ny][nx])
					continue;
                 //x일 경우 따로 tmp에 저장해 놓는다.
				if (board[ny][nx] == 'X') {
					tmp.push({ nx, ny });
					visitswan[ny][nx] = visitswan[y][x] + 1;
				}
                //.일 경우 그대로 탐색 진행한다.
				else if (board[ny][nx] == '.') {
					swanq.push({ nx, ny });
					visitswan[ny][nx] = visitswan[y][x] + 1;
				}
				else if (ny == endY && nx == endX) {

					return;
				}
				
			}
		}
		swanq = tmp;
	}
	
}

int main() {

	char symbol;
	cin >> R >> C;
	int flag = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> symbol;
			board[i][j] = symbol;
			if (symbol == 'L') {
				if (flag == 0)
				{
					startX = j;
					startY = i;
					waterq.push({ j, i });
					visitwater[i][j] = 1;
					swanq.push({ j, i });
					visitswan[i][j] = 1;
					flag = 1;
				}
				else
				{
					endX = j;
					endY = i;
					waterq.push({ j, i });
					visitwater[i][j] = 1;
				}
			}
			else if (symbol == '.') {
				waterq.push({ j, i });
				visitwater[i][j] = 1;
			}
		}
	}
	watermelt();
	cout << day;

}
/*
4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

1 9
L.XX.XX.L

1 7
LXX.XXL
*/