[BAEKJOON] 2206 벽 부수고 이동하기 (C++)

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

2206번: 벽 부수고 이동하기

 

하루종일 삽질을 했다. 진짜 질문하기 테스트케이스 다 해봤는데, 안됐는데...

초기 거리값들을 100000에서 1000000으로 수정해주니까 통과했다. 1000* 1000이 백만이라는 걸 방금 이 문장을 쓰면서 깨달았다...... 구몬 등록하러 가야하나

 

 

문제

탐색 문제지만 특이한 조건이 포함돼있다. 벽이 존재하는 곳은 갈 수 없지만, 단 한 번 벽을 부수고 이동할 수 있다.

(1,1)지점에서 (N,M)지점까지 이동하는 최단거리를 구하는 문제

 

접근

탐색과정에서 벽을 부쉈는지 여부를 같이 전달한다.

Case는 다음과 같이 3가지 존재한다.

1. 벽을 이미 부수고 온 경우 -> 벽이 없는 곳으로만 이동한다.

2. 벽을 부수지 않은 경우 

2-1. 벽이 있는 곳 -> 벽을 부쉈는지 여부(check)를 true로 업데이트 하고 해당 위치를 방문한다.

2-2. 벽이 없는 곳 -> check를 업데이트 하지 않고 해당 위치를 방문한다.

 

풀이

처음에 dfs로 풀이를 했는데, 시간초과가 발생했다.

dfs로도 조건을 잘 설정하면 풀 수 있는 것 같긴 한데, 일단 최단거리는 그냥 기계적으로 bfs하는 게 맞는 것 같기도 하다.

 

기본적인 bfs를 진행하되, 벽을 부쉈는지 여부 check를 같이 확인한다.

따라서 bfs진행과정에서 사용하는 queue의 형식을 pair<pair<int,int>,int>로 하여 좌표값과 check에 해당하는 값을 전달한다.

탐색을 하며 다음 방문할 위치가 벽인경우와 벽이 아닌 경우로 나누어 탐색한다.

1. 벽인 경우

이미 벽을 부순 경우는 방문할 수 없다.

벽을 부수지 않은 경우 check값을 업데이트 하고 방문 필요 여부를 확인한다.(이미 더 적은 거리값으로 방문한 경우는 방문할 필요가 없다.)

2. 벽이 아닌 경우

check 값을 그대로 전달하며 방문 필요여부를 확인한다.

 

거리값을 기록하는 배열 Visited도 3차원배열로 선언하여 각각의 좌표마다 벽을 부수고 온 경우와 벽을 부수지 않고 온 경우를 모두 기록하였다.

 

또 입력을 string으로 받지 않아서 삽질을 했었는데... 입력이 서로 붙어있는지 확인하고 입력받는 형식을 적절히 작성할 필요가 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"

using namespace std;

int N, M, ans;
int MAP[1001][1001];
int Visited[1001][1001][2];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1};
queue<pair<pair<int, int>,int>> Q;
void Input() {
	cin >> N>>M;
	string s;
	for (int i = 1; i <= N; i++) {
		cin >> s;
		for (int j = 0; j < M; j++) {
			MAP[i][j+1] = s[j] - '0';
			Visited[i][j+1][0] = 1000000;
			Visited[i][j+1][1] = 1000000;
		}
	}
}

void Solve() {
	int x, y, xx, yy, check;
	Visited[1][1][0] = 1;
	Q.push({ {1,1},0 });
	while (!Q.empty()) {
		x = Q.front().first.second; y = Q.front().first.first; check = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			xx = x + dx[i]; yy = y + dy[i]; 

			if (xx<1 || xx>M || yy<1 || yy>N) continue;

			if (MAP[yy][xx] == 1) {
				if (check == 1) continue;
				if (Visited[yy][xx][1] > Visited[y][x][check] + 1) {
					Visited[yy][xx][1] = Visited[y][x][check] + 1;
					Q.push({ {yy,xx}, 1});
				}
			}
			if (MAP[yy][xx] == 0) {
				if (Visited[yy][xx][check] > Visited[y][x][check] + 1) {
					Visited[yy][xx][check] = Visited[y][x][check] + 1;
					Q.push({ {yy,xx}, check });
				}
			}
		}
	}
	ans = min(Visited[N][M][0], Visited[N][M][1]);

	if (ans == 1000000) cout << -1<<endl;
	else cout << ans << endl;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();


	return 0;
}