c++ 백준_2206_"벽 부수고 이동하기"

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

2206번: 벽 부수고 이동하기

 

 

BFS를 사용하여 풀었다.

​

방문 체크는

벽을 부순 경우와 안부순 경우

두 개의 경우를 고려해 방문을 체크했다.

​

두개를 고려하지않으면

벽을 부수고 난 뒤 간 좌표를

벽을 안부수고 간 경로에서 다시 방문을 못 할 수도 있기 때문이다.

 

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

int N, M;
int board[1001][1001];
bool visit[1001][1001][2];

pair<int, int> dir[] = { {-1,0},{0,1},{1,0},{0,-1} };

typedef struct {
	int x, y;
	int cnt;
	int wall_cnt;
}node;

bool is_in(int x, int y) {
	if (x < 1 || y < 1 || x> N|| y >M)
		return false;
	return true;
}

void find_path() {

	
	queue<node> q;

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

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		int wall_cnt = q.front().wall_cnt;
		q.pop();

		if (x == N && y == M) {
			cout << cnt;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int dx = dir[i].first;
			int dy = dir[i].second;

			if (is_in(x + dx, y + dy)) {
				
				if (board[x + dx][y + dy] == 1) {

					if (wall_cnt == 0 && !visit[x+dx][y+dy][1]) {
						q.push({ x + dx,y + dy,cnt + 1,1 });
						visit[x + dx][y + dy][1] = true;
					}

				}
				else {
					if (wall_cnt) {
						if (!visit[x + dx][y + dy][1]) {
							visit[x + dx][y + dy][1] = true;
							q.push({ x + dx,y + dy,cnt + 1,wall_cnt });
						}
					}
					else {
						if (!visit[x + dx][y + dy][0]) {
							visit[x + dx][y + dy][0] = true;
							q.push({ x + dx,y + dy,cnt + 1,wall_cnt });
						}
					}
				}


			}
		}


	}
	
	cout << "-1";
}

int main(void) {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		string temp;
		cin >> temp;
		for (int j = 1; j <= M; j++) {
			board[i][j] = temp[j - 1] - '0';
		}
	}

	find_path();

}