백준 16441 : 아기돼지와 늑대

문제 설명

---

문제에서 주어진 고리분지는 N × M 크기의 격자로, 초원, 빙판, 산으로 이루어져 있다. 늑대는 산을 제외한 칸으로 이동하며, 빙판에서는 초원이나 산에 부딪칠 때까지 미끄러진다. 이때 지도에서 늑대가 도달할 수 없는 초원인 칸들을 '안전한 곳'으로 표시하는 프로그램을 작성하시오. (3 ≤ N, M ≤ 100)

---

 

N, M범위가 작음으로, 전체탐색으로 충분히 풀리는 문제라는 것을 알 수 있다. 얼음에서의 이동을 구현하기 위해 queue에 3개의 변수를 구조체로 잡아 사용했다. 현재 좌표값 x, y와 전칸에서 현재 칸으로 넘어올때의 방향을 이용해 queue를 잡고 얼음이라면 전에서의 방향대로 계속 움직이게끔 구현하였다.

1. 현재칸이 얼음이라면 

    - 가야하는 방향에 산이있다면 : 4방검사를 진행한다.

    - 아니라면 : 그 방향대로 직진한다.

2. 현재칸이 초원이라면 : 평범한 4방검사를 통해 탐색을 진행한다.

해당 방법으로 BFS를 구현하여 문제를 해결했다.

#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
char map[110][110];
bool ch[110][110][5];
int safe[110][110];
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };

struct dat {
	int x, y, loc;
};

void BFS(int x, int y)
{
	int i;
	queue <dat> q;
	q.push({ x, y, 0 });
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y;
		int n_lo = q.front().loc;
		q.pop();
		if (map[n_x][n_y] == '+') {
			int nx = n_x + dx[n_lo], ny = n_y + dy[n_lo];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || ch[nx][ny][n_lo] == 1) continue;
			else {
				if (map[nx][ny] == '#') {
					for (i = 0; i < 4; i++) {
						int fx = n_x + dx[i], fy = n_y + dy[i];
						if (fx < 0 || fy < 0 || fx >= n || fy >= m || ch[fx][fy][i] == 1 || map[fx][fy] == '#') continue;
						else {
							safe[fx][fy] = 1;
							ch[fx][fy][i] = 1;
							q.push({ fx, fy, i });
						}
					}
				}
				else {
					safe[nx][ny] = 1;
					ch[nx][ny][n_lo] = 1;
					q.push({ nx, ny, n_lo });
				}
			}
		}
		else {
			for (i = 0; i < 4; i++) {
				int nx = n_x + dx[i], ny = n_y + dy[i];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m || ch[nx][ny][i] == 1 || map[nx][ny] == '#') continue;
				else {
					ch[nx][ny][i] = 1;
					safe[nx][ny] = 1;
					q.push({ nx, ny, i });
				}
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%s", map[i]);
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (map[i][j] == 'W') {
				safe[i][j] = 1;
				BFS(i, j);
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (safe[i][j] == 0 && map[i][j] == '.') printf("P");
			else printf("%c", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}

소스가 많이 비효율 적인것 같다. ch배열을 2차원으로 해도 되는 방법이 있는것 같은데 다음번에 시도해봐야겠다.