백준 3055번 탈출

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

3055번: 탈출

 

 

 

 

 

<접근방법>

전형적인 bfs문제입니다.

물이 퍼질 곳은 고슴도치가 갈 수 없다고 했습니다.

말 그대로 구현하면 조금 어려울 것 같습니다.

 

한 타임에 물, 고슴도치 두 개 모두 움직입니다.

그럼 물을 먼저 움직이게 하면 됩니다.

이미 물이 있는 곳은 고슴도치가 갈 수 없으니까요.

 

다른 두 개의 객체를 따로 이동시켜야 합니다.

이를 위해서 큐 두 개를 사용합니다.

그리고 두 개를 따로 돌립니다.

이를 위한 기법은 코드를 참고하시면 됩니다.

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int y, x, t;
};

int n, m;
char map[51][51];
bool visit_q[51][51];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

queue <point> q;
queue <point> w;

int bfs() {
	while (!q.empty()) {
		int sz_w = w.size();
		for (int z = 0; z < sz_w; z++) {
			point t = w.front();
			w.pop();

			for (int i = 0; i < 4; i++) {
				int ty = t.y + dy[i];
				int tx = t.x + dx[i];
				int tt = t.t + 1;

				if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;

				if (map[ty][tx] == '.') {
					w.push({ ty, tx, tt });
					map[ty][tx] = '*';
				}
			}
		}

		int sz_q = q.size();
		for (int z = 0; z < sz_q; z++) {
			point t = q.front();
			q.pop();

			if (map[t.y][t.x] == 'D') return t.t;

			for (int i = 0; i < 4; i++) {
				int ty = t.y + dy[i];
				int tx = t.x + dx[i];
				int tt = t.t + 1;

				if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
				if (visit_q[ty][tx] || map[ty][tx] == 'X' || map[ty][tx] == '*') continue;

				q.push({ ty, tx, tt });
				visit_q[ty][tx] = true;
			}
		}
	}
	return -1;
}

int main() {
	point t;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'S') {
				q.push({ i, j, 0 });
				visit_q[i][j] = true;
				t.y = i; t.x = j;
			}
			else if (map[i][j] == '*') {
				w.push({ i, j, 0 });
			}
		}
	}

	int res = bfs();
	if (res == -1) {
		cout << "KAKTUS" << '\n';
	}
	else {
		cout << res << '\n';
	}

	return 0;
}

 

 

---

 

 

<느낀 점>

- 물 bfs를 돌릴 때, 방문체크를 사용할 필요가 없게 할 수도 있다.