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

백준 2206 벽 부수고 이동하기

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

• 맵에서 가장 적은 개수의 칸을 지나는 경로 찾기
  -> 가중치가 모두 같은 경우의 최단거리를 구하기
  -> 너비 우선 탐색 (BFS)

#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

const int MAXN = 1000;
const int IMPOSSIBLE = 2000000;

int N, M;
string mp[MAXN + 2];
bool isVisited[MAXN + 2][MAXN + 2][2] = { 0 };
queue<pair<pair<int, int>, pair<int,int>>> que;
//pair<pair<r좌표, c좌표>, pair<state, dist> 저장
//state 0: 벽 부술 수 없음
//state 1: 벽 하나 부술 수 있음
int dirR[4] = {-1,0,0,1};
int dirC[4] = {0,-1,1,0};


int bfs() {
	//시작 좌표 
	que.push(make_pair(make_pair(1, 1), make_pair(1, 1)));

	int minDist = IMPOSSIBLE;
	while (!que.empty()) {
		pair<pair<int, int>, pair<int, int>> cur = que.front();
		que.pop();

		int curR = cur.first.first;
		int curC = cur.first.second;
		int curState = cur.second.first;
		int curDist = cur.second.second;

		//이미 방문한 선택지면 건너뛰기
		if (isVisited[curR][curC][curState]) 
			continue; 
		//방문 체크
		isVisited[curR][curC][curState] = true;

		//도착 좌표인 경우 minDist 갱신
		if (curR == N && curC == M) {
			minDist = min(minDist, curDist);
			continue;
		}
		
		//현재 좌표 벽 유무 확인
		if (mp[curR][curC] == '1') {
			//벽 부수기
			if (curState == 1) curState = 0;
			//벽을 부술 수 없는 상태인 경우 더이상 이동할 수 없다
			else continue;
		}

		//다음 좌표로 이동
		for (int i = 0; i < 4; i++) {
			int nextR = curR + dirR[i];
			int nextC = curC + dirC[i];

			if (nextR < 1 || nextR > N) continue;
			if (nextC < 1 || nextC > M) continue;

			que.push(make_pair(make_pair(nextR, nextC), make_pair(curState, curDist + 1)));
		}
	}

	if (minDist == IMPOSSIBLE) return -1;
	return minDist;
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string input;
		cin >> input;
		//string의 인덱스를 1부터 검사할 수 있도록
		//input의 맨 앞에 의미없는 문자 하나를 붙임
		mp[i] = "0" + input;
	}
	
	cout << bfs();
	return 0;
}