[G3] 백준 16441번 아기돼지와 늑대 C++ 너비 우선 탐색, 시뮬레이션

리뷰

 

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

오랜만에 풀어본 BFS + 시뮬레이션 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 맵의 세로/가로 크기를 저장할 변수
• arr : 맵 초기 정보를 저장할 2차원 문자 배열
• v : 방문 여부를 체크하기 위한 2차원 논리형 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 늑대의 좌표 정보를 정의할 구조체
• wolfs : 초기 늑대 위치를 저장할 Pos타입 큐

 

함수

1. bfs

void bfs(Pos& wolf) {
	queue<Pos> q;
	q.push(wolf);
	v[wolf.cx][wolf.cy] = true;

	while (!q.empty()) {
		auto [cx, cy] = q.front(); q.pop();

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			
			if (arr[nx][ny] == '.' && !v[nx][ny]) {
				v[nx][ny] = true;
				q.push({ nx, ny });
			}

			while (arr[nx][ny] == '+') {
				nx += dx[i];
				ny += dy[i];
			}

			if (arr[nx][ny] == '.') {
				if (v[nx][ny]) continue;
				v[nx][ny] = true;
				q.push({ nx, ny });
			}

			if (arr[nx][ny] == '#') {
				nx -= dx[i];
				ny -= dy[i];

				if (v[nx][ny]) continue;
				v[nx][ny] = true;
				q.push({ nx, ny });
			}
		}
	}
}

 

늑대가 갈 수 있는 위치를 모두 방문하는 시뮬레이션 하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, n*m크기의 맵 정보를 입력 받아 arr배열을 초기화한다.
2. 만약 격자에 'W'가 주어진 경우 wolfs에 좌표 정보를 push해준다.
3. wolfs가 빌때까지 while루프를 순회하며 매 루프마다 요소를 꺼내 Pos타입 변수 wolf에 저장한다.
4. bfs함수의 매개변수로 wolf를 전달하여 시뮬레이션을 수행한다.
5. bfs함수 내부에선 wolf의 좌표를 Pos타입 큐 q에 추가하고, 초기 좌표에 방문 처리를 해준다.
6. 이동한 위치가 초원이라면 이동을 진행하고, 빙판일 경우 산이나 초원을 만날 때 까지 이동을 계속 진행한다.
7. 모든 시뮬레이션을 마친 후 맵을 순회하며 초원이면서 늑대가 방문하지 않은 경우 P를 출력한다.
8. 그 외의 경우엔 arr배열에 저장된 문자를 그대로 출력해주면 된다.

 

트러블 슈팅

1. 빙판길을 미끄러지는 경우를 시뮬레이션할때 방문처리에 이슈가 있어 WA를 받았다.
2. 빙판길을 이용하던 도중 산을 만나거나 초원을 만난 경우를 분기처리해 주어 AC를 받았다.

 

참고 사항

1. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러진다.
2. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있다.
3. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원이다.
4. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산이다.

 

정답 코드

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

const int N = 100;
int n, m;
char arr[N][N];
bool v[N][N];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int cx, cy;
};
queue<Pos> wolfs;

void bfs(Pos& wolf) {
	queue<Pos> q;
	q.push(wolf);
	v[wolf.cx][wolf.cy] = true;

	while (!q.empty()) {
		auto [cx, cy] = q.front(); q.pop();

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			
			if (arr[nx][ny] == '.' && !v[nx][ny]) {
				v[nx][ny] = true;
				q.push({ nx, ny });
			}

			while (arr[nx][ny] == '+') {
				nx += dx[i];
				ny += dy[i];
			}

			if (arr[nx][ny] == '.') {
				if (v[nx][ny]) continue;
				v[nx][ny] = true;
				q.push({ nx, ny });
			}

			if (arr[nx][ny] == '#') {
				nx -= dx[i];
				ny -= dy[i];

				if (v[nx][ny]) continue;
				v[nx][ny] = true;
				q.push({ nx, ny });
			}
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> arr[i][j];
			if (arr[i][j] == 'W') wolfs.push({i, j});
		}
	}

	while (!wolfs.empty()) {
		Pos wolf = wolfs.front(); wolfs.pop();
		bfs(wolf);
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (arr[i][j] == '.' && !v[i][j]) cout << 'P';
			else cout << arr[i][j];
		}
		cout << "\n";
	}
}