[백준] 2206번 - 벽 부수고 이동하기

링크

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

2206번: 벽 부수고 이동하기

풀이

시작점에서 끝점까지 이동하는데 걸리는 최소 시간을 구하는 문제이다. 저는 최소를 보자마자 BFS가 떠올랐고, 여기서 하나의 조건을 주었는데 벽을 하나정도는 부시고 갈수 있다는 것이다.

 

고민을 하다 일반적인 BFS를 이용할때는 방문했던 지점을 또 못가도록 방문체크 배열을 하나 만들어 방문 여부를 판단 하였었다.

 

이 방문체크 배열에 내가 같은 x, y 지점에 도착하였을때 문을 부수고 왔는지

아니면 그냥 왔는지라는 조건을 같이 추가하기 위해

2차원 방문 체크 배열이 아닌 3차월 방문 체크 배열을 만들어 이용하였다.

 

visited[X][Y][문을부수고온 횟수] 이런 식으로 만들어 방문 체크를 하였고 BFS를 통하여 문제를 해결 하였다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define SIZE 1010

using namespace std;

typedef long long int ll;
typedef struct Data {
	int x, y, cnt, wall;
}Data;
const int INF = 2000000000;


char board[SIZE][SIZE];
bool visited[SIZE][SIZE][2];

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M; cin >> N >> M;

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

	Data s;
	s.x = 0; s.y = 0, s.cnt = 1, s.wall = 0;

	queue<Data> q;

	q.push(s);

	while (!q.empty()) {
		Data h = q.front();
		q.pop();

		visited[s.x][s.y][s.wall] = true;

		if (h.x == N - 1 && h.y == M - 1) {
			cout << h.cnt;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			Data n;
			n.x = h.x + dx[i], n.y = h.y + dy[i], n.cnt = h.cnt + 1; 
			n.wall = h.wall + board[n.x][n.y] - '0';

			if (n.x < 0 || n.x >= N || n.y < 0 || n.y >= M)
				continue;
			if (visited[n.x][n.y][n.wall] == true)
				continue;
			if (n.wall > 1)
				continue;

			visited[n.x][n.y][n.wall] = true;
			q.push(n);
		}
	}

	cout << -1;
	return 0;
}