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

📌 문제

BOJ 바로가기

이모티콘 문제와 상당히 유사하다고 느꼈다. 벽 부수고 이동하기 문제를 더 연습해보고 싶으신 분들은 이모티콘 문제를 풀어보면 좋을 것 같다!

단순 BFS에 조건이 하나 더 추가된 문제이다. 0(길)과 1(벽)이 적힌 지도가 입력으로 주어진다. (1, 1)부터 (N, M)까지의 최단거리를 구하되 벽을 한 번 부술 수 있는 기회를 사용할 수 있다.

🗡 풀이

디버깅하느라 몇 시간 쓴 듯한 느낌적인 느낌.. 😭 이번에도 진짜 어이없는 걸로 시간 엄청 걸렸다. 0이랑 1을 잘못 써서 시간 한참 쓰고, 0 <= nx && nx <= n 이렇게 써야 할 것을 0 <= nx && nx <= 1000 으로 써서 시간 한참 썼다... 언제쯤이면 이런 바보같은 실수가 줄어들까ㅠㅠㅠㅠ

📍 벽을 부술 수 있는 기회를 소진한 경우의 최단거리와 벽을 부수지 않은 상태에서의 최단거리 배열을 따로 선언해주어야 한다. visited 배열도 마찬가지! 나같은 경우는 visited 배열을 -1 로 초기화해두고 최단거리 배열을 겸해서 썼다.

질문게시판의 반례 모음 페이지 가 많은 분들께 도움이 될 것 같다. 고수님들 너무 대단하시다.

🚩 소스코드

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

int n, m, map[1001][1001];
int visited[1001][1001][2]; // 거리 배열 역할 동시에 수행

int main() {
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			scanf("%1d", &map[i][j]);
	}
	// visited 배열 초기화
	memset(visited, -1, sizeof(visited));
	// BFS
	queue <tuple<int, int, int >> q;
	q.push({ 1, 1, 0 });
	visited[1][1][0] = 1;
	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int broken = get<2>(q.front());
		if (x == n && y == m) {
			if (broken)
				cout << visited[n][m][1];
			else
				cout << visited[n][m][0];
			return 0;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			// 벽을 부순 적 없고 벽을 마주쳐서 부수는 경우
			if (1 <= nx && nx <= n && 1 <= ny && ny <= m && visited[nx][ny][1] == -1 && !broken && map[nx][ny] == 1) {
				q.push({ nx, ny, 1 });
				visited[nx][ny][1] = visited[x][y][0] + 1;
			}
			// 벽을 부순 적 없고 길이 뚫려있는 경우
			else if (1 <= nx && nx <= n && 1 <= ny && ny <= m && visited[nx][ny][0] == -1 && !broken && map[nx][ny] == 0) {
				q.push({ nx, ny, 0 });
				visited[nx][ny][0] = visited[x][y][0] + 1;
			}
			// 벽을 부순 적 있고 길이 뚫려있는 경우
			else if (1 <= nx && nx <= n && 1 <= ny && ny <= m && visited[nx][ny][1] == -1 && broken && map[nx][ny] == 0) {
				q.push({ nx, ny, 1 });
				visited[nx][ny][1] = visited[x][y][1] + 1;
			}
		}
	}
	cout << "-1";
	return 0;
}