백준 3055번: 탈출 - BFS C++

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

3055번: 탈출

1.문제설명

3 6
D...*.
.X.X..
....S.

물은 상하좌우로 퍼진다. 고슴도치는 상하좌우로 한 칸 씩 이동할 수 있다

X는 물, 고슴도치 모두 지날 수 없다

D는 고슴도치만 갈 수 있다.

 

고슴도치가 물을 피해 D로 갈 수 있다면 최소 시간을 출력하고,

그럴 수 없다면 문제에서 제시한 문자열을 출력해준다.

 

---

2.접근 방법[알고리즘]

1. 물을 상하좌우로 퍼트린다.

2. 고슴도치를 물이 없는 곳으로 상하좌우 이동시킨다.

3. 1,2를 반복하면서 고슴도치가 D를 방문하면 시간을 출력하고 종료한다.

4. D를 방문할 수 없으면 "KAKTUS" 를 출력한다.

 

 

이 문제에서 물과 고슴도치 모두 BFS를 동시에 해주어야 한다.

각각의 큐를 만들고 시간을 증가시키면서 새로 방문한 노드에 대해서 일괄적으로 상하좌우 탐색한다.

고슴도치는 물이 방문할 점을 방문할 수 없기 때문에

물 -> 고슴도치 -> 물 -> 고슴도치 순으로 BFS를 돈다.

 

 

---

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int r, c;
char arr[53][53];
bool s_check[53][53], wt_check[53][53];
int ch[53][53];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
//물 먼저 이동 후 고슴도치 이동

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;
	queue<pair<int, int> > wt;
	queue<pair<int, int> > s;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '*') {
				ch[i][j] = -1;
				wt.push({ i,j });
				wt_check[i][j] = 1;
			}
			else if (arr[i][j] == 'S') {
				ch[i][j] = 1;
				s.push({ i,j });
				s_check[i][j] = 1;
			}
			else if (arr[i][j] == 'X') {
				ch[i][j] = 2;
			}
			else if (arr[i][j] == 'D') {
				ch[i][j] = 3;
			}
		}
	}
	int t = 0;
	while (true) {

		int s_size = s.size();
		int wt_size = wt.size();

		if (s_size == 0) break;

		for (int i = 0; i < wt_size; i++) {
			int x = wt.front().first;
			int y = wt.front().second;
			wt.pop();

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

				if (nx <= 0 || nx > r || ny <= 0 || ny > c||wt_check[nx][ny] == 1) continue;
				if (ch[nx][ny] == 0 || ch[nx][ny]==1) {
					wt_check[nx][ny] = 1;
					ch[nx][ny] = -1;
					wt.push({ nx,ny });
				}
			}
		}

		for (int i = 0; i < s_size; i++) {
			int x = s.front().first;
			int y = s.front().second;
			s.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if (nx <= 0 || nx > r || ny <= 0 || ny > c || s_check[nx][ny] == 1) continue;
				if (ch[nx][ny] == 0 || ch[nx][ny] == 1 ) {
					ch[nx][ny] = 1;
					s_check[nx][ny] = 1;
					s.push({ nx,ny });
				}
				else if (ch[nx][ny] == 3) {
					cout << t+1;
					return 0;
				}
			}

		}
		t++;
		//print();
	}

	cout << "KAKTUS" << '\n';

	return 0;
}

백준 3055번 탈출 메모리 시간

틀린이유

처음에 고슴도치와 물이 방문한 좌표를 체크해주지 않아 틀렸다

BFS든 DFS든 방문해준 점을 체크표시해주지 않으면 방문한 곳을 계속 방문해서 무한 루프에 빠지고 만다.

그로 인해 시간초과나 메모리초과가 발생한다.