BOJ 3055

시뮬레이터 문제이다.

어디서 참고한 코드 같지만, 출처는 기억이 나지 않는다.

 

문제를 풀기 위하여 bfs()를 한번만 돌릴 수도 있지만, 시뮬레이터 재현을 위해 '물'과 '고슴도치'의 이동을 한번씩 하게 하였다.

 

여기서 핵심은 moveWater(), moveHedge() 함수의 while(qsize--)

이렇게 하면, 시간 순서상으로 한번씩 Stage 각각 넘어갈 수 있게 된다.

 

bfs 혹은 큐를 이용한 문제에서 사용할 수 있는 좋은 테크닉이라 기록에 남긴다. 

 

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

int r, c;
const int HEDGE = 0;
const int WATER = 1;

char Map[50][50];
bool visit[50][50][2];

// 상하좌우
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

queue <pair<int, int>> q[2];

void moveWater() {
	int qsize = q[WATER].size();
	while (qsize--) {
		int y = q[WATER].front().first;
		int x = q[WATER].front().second;
		q[WATER].pop();

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

			// boundary
			if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			// visit or beeber's cave or stone
			if (visit[ny][nx][WATER] || Map[ny][nx] == 'D' || Map[ny][nx] == 'X') continue;

			visit[ny][nx][WATER] = true;
			Map[ny][nx] = '*';
			q[WATER].push({ ny,nx });
		}
	}
}

bool moveHedge() {
	int qsize = q[HEDGE].size();
	while (qsize--) {
		int y = q[HEDGE].front().first;
		int x = q[HEDGE].front().second;
		q[HEDGE].pop();

		// found
		if (Map[y][x] == 'D') { return true; }

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

			// boundary
			if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			// visit or water or stone
			if (visit[ny][nx][HEDGE] || Map[ny][nx] == '*' || Map[ny][nx] == 'X' ) continue;

			visit[ny][nx][HEDGE] = true;
			q[HEDGE].push({ ny,nx });
		}
	}
	return false;
}

void simulate() {
	int time = -1;
	while (true) {
		moveWater();
		bool escape = moveHedge();
		time++;
		// success
		if (escape) { cout << time << '\n'; break; }

		// fail
		if (q[HEDGE].empty()) { cout << "KAKTUS" << '\n'; break; }
	}
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> Map[i][j];
			// hedge
			if (Map[i][j] == 'S') {
				visit[i][j][HEDGE] = true;
				q[HEDGE].push({ i,j });
			}
			else if (Map[i][j] == '*') {
				visit[i][j][WATER] = true;
				q[WATER].push({ i,j });
			}
		}
	}
	simulate();
	return 0;
}

 

[Reference]

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