[백준] 탈출 (3055/C++)

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

3055번: 탈출

 

코드 설명

큐를 2개를 이용하였다. start큐는 이동하는 경로, water 큐는 물의 경로이다.

일반 BFS while()문 내에 각각의 큐를 넣어 반복하였다.

 

전체 while()문 내에

 

1. 먼저 물 4방향씩 이동 ( 이동 후 물(*) 찍어주기)

2. 이후 고슴도치 4방향 탐색 이동 ( visited배열 사용했습니다)

3. 하루 증가

과 같이 계속해서 반복해주었습니다. 

 

 

배운점!!

매번 BFS를 이용하여 끝까지 탐색하는것만 생각했는데 큐의 사이즈를 이용 +  이중while문  활용 하여 한칸씩 이동후 검사하는 방법!

 

코드 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char map[51][51];
int R, C;

bool flag;
bool visited[51][51];
beaver target;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int cnt;
queue<pair<int, int>> start;
queue<pair<int, int>> water;
void BFS() {
	

	while (!start.empty()) { // 전체 while
		cnt++; // 날짜하루증가
		int w_size = water.size();
		while (w_size--) { //물먼저이동

			int y = water.front().first;
			int x = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
				if (map[ny][nx] == '*' || map[ny][nx] == 'X'||map[ny][nx]=='D') continue;
				map[ny][nx] = '*'; //맵에 물 표기 
				water.push({ ny,nx });

			}

		}

		//S이동
		int s_size = start.size();
		visited[start.front().first][start.front().second] = true;
		while (s_size--) {
			int y = start.front().first;
			int x = start.front().second;
			if (map[y][x] == 'D') { //도착
				cout << cnt - 1;
				flag = true;
			}
			start.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
				if (map[ny][nx] == '*' ||map[ny][nx] == 'X') continue;
				if (!visited[ny][nx]) {
					visited[ny][nx] = true;
					start.push({ ny,nx });


				}
			}



		}




	}
	if (flag == false) cout << "KAKTUS"; //비버굴 만나지 못한경우 
	



}

int main() {

	cin >> R >> C;
	for (int y = 0; y < R; y++) {
		for (int x = 0; x < C; x++) {
			cin >> map[y][x];

			if (map[y][x] == 'S') {
				start.push({ y,x });

			}
			else if (map[y][x] == '*') {
				water.push({ y,x });
			}



		}
	}


	BFS();



	return 0;
}