백준 2206 C++ (BFS)

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

2206번: 벽 부수고 이동하기

 

 

벽을 부수지 않으면 아주 간단한 BFS문제이다.

벽을 부수는 경우, 벽을 부수지 않는 경우로 경로를 나눠서 저장하면 된다.

 

1. 안가본 길이며 '0'인 경우에 계속 탐색을 이어가고
2. 안가본 길이며 '1'인 경우 => 벽을 부순적이 없다 => 벽은 부순 경로로 탐색

 

코드로 나타내면 아래와 같다.

int dist[1010][1010][2];

// ...
queue<tuple<int, int, int>> Q;

// ...
tie(x, y, wall) = Q.front();

// ...
//안가본 길이며(dist == -1) '0'인 경우에 계속 탐색을 이어가고
if (board[nx][ny] == '0' && dist[nx][ny][wall] == -1) {
	dist[nx][ny][wall] = dist[x][y][wall] + 1;
	Q.push({ nx, ny, wall });
}
//안가본 길이며 '1'인 경우 => 벽을 부순적이 없다(wall == 0) => 벽은 부순 경로로 탐색을 이어감
if (!wall && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
	dist[nx][ny][1] = dist[x][y][wall] + 1;
	Q.push({ nx, ny, 1 });
}

dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 까지의 거리
dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 까지의 거리

 

벽을 부수면 dist[x][y][1]로 넘어오는, 한 층을 올라와서 탐색하는 느낌이다.

 

위의 부분만 고려하면 나머진 간단한 bfs문제와 같다!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int N, M;
char board[1010][1010];
int dist[1010][1010][2];
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 >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			dist[i][j][0] = dist[i][j][1] = -1;
            
	dist[0][0][0] = dist[0][0][1] = 1;

	queue<tuple<int, int, int>> Q;
	Q.push({ 0, 0, 0 });

	while (!Q.empty()) {
		int x, y, wall;
		tie(x, y, wall) = Q.front();
		Q.pop();
		if (x == N - 1 && y == M - 1) {
			cout << dist[x][y][wall] << '\n'; 
			return 0;
		}
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (board[nx][ny] == '0' && dist[nx][ny][wall] == -1) {
				dist[nx][ny][wall] = dist[x][y][wall] + 1;
				Q.push({ nx, ny, wall });
			}
			if (!wall && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
				dist[nx][ny][1] = dist[x][y][wall] + 1;
				Q.push({ nx, ny, 1 });
			}
		}
	}

	cout << -1 << '\n';
	return 0;
}

 

조금 난이도가 있는 문제들은 3차원 배열로 다른 경우의 수를 저장하는 방식이 많은것 같다.

 

3차원 배열을 어떻게 적극적으로 사용할지에 대해 문제를 풀때 고민을 많이 해봐야겠다.

 

이 문제의 다음 문제이다. 조금 응용된 버전으로 같이 보면 좋을듯 하다.

https://mumu3997.tistory.com/11

백준 14442 (BFS) C++