[백준 BOJ][C++]2206번 벽 부수고 이동하기 풀이: BFS

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

2206번: 벽 부수고 이동하기

 

 이 문제는 BFS 로 해결할 수 있습니다. 

 

 이때 각 위치까지의 경로가 벽을 한 번 부시고 왔을 수도, 아닐 수도 있기 때문에 두 가지 방문 표시를 사용해야 합니다. 

 visit[y][x][0] = (x, y) 위치까지의 경로에서 벽을 한 칸도 부시지 않았을 때의 방문 표시

 visit[y][x][1] = (x, y) 위치까지의 경로에서 벽을 한 칸 부셨을 때의 방문 표시

 

 node 구조체는 각 칸의 위치정보와, depth(경로의 길이), flag(현재까지의 경로에서 벽을 부셨다면 1, 부시지 않았다면 0)으로 이루어져있습니다. 

 

[풀이 과정]

1. 시작 위치의 정보 x=0, y=0, depth=1, flag=0 을 queue에 푸시한 후, 방문 표시 visit[0][0][0]을 한다. 

2. queue에서 원소를 pop 한다. 

3. pop한 원소의 위치 정보가 map의 마지막 위치라면 해당 원소의 depth(경로의 길이)를 반환한다. 

4. 현재 위치에서 상/하/좌/우 중 이동 가능한 다음 위치를 탐색한다. 

4-1. 다음 위치의 원소가 1이고 아직 벽을 부시지 않았다면, 벽을 부셨다는 방문 표시 후, queue에 push한다.

4-2. 다음 위치의 원소가 0이고 방문하지 않았다면, 방문 표시 후 queue에 push 한다. 

5. map의 마지막 위치 혹은 queue가 empty일 때까지 2~4 과정을 반복한다. 

6. 만약 queue가 empty일 때까지 마지막 위치를 찾지 못했다면 경로를 찾지 못한것이므로 -1을 반환한다. 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

#define MAX 1001

typedef struct node {
	int x;
	int y;
	int depth;
	int flag;
};

int n, m;
int map[MAX][MAX];
bool visit[MAX][MAX][2] = { false, };

int bfs() {

	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };

	queue<node> q;

	visit[0][0][0] = true;
	q.push({ 0, 0, 1, false });

	while (!q.empty()) {
		node curr = q.front();
		q.pop();


		if (curr.x == m - 1 && curr.y == n - 1) {
			return curr.depth;
		}

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

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

			if (map[ty][tx] == 1 && curr.flag == 0) {
				visit[ty][tx][curr.flag + 1] = true;
				q.push({ tx, ty, curr.depth + 1, curr.flag + 1 });
			}
			else if (map[ty][tx] == 0 && !visit[ty][tx][curr.flag]) {
				visit[ty][tx][curr.flag] = true;
				q.push({ tx, ty, curr.depth + 1, curr.flag });
			}
		}

	}
	return -1;
}

int main(void) {
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++) {
			map[i][j] = temp[j] - 48;
		}
	}

	cout << bfs();

	return 0;
}