[백준 / C++] 2206번: 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

난이도: solved.ac 골드 3

 

알고리즘 분류

그래프 탐색, 너비 우선 탐색(BFS)

 

접근 방법

지금까지 풀었던 BFS 문제에서 사용했던 visited 배열에 한 차원을 더 추가시켜 벽을 부순 적이 없는 상태에서의 방문 표시는 visited[][][0]에 나타내고, 벽을 부순 적이 있는 상태에서의 방문 표시는 visited[][][1]에 나타내었다.

 

큐에는 현재 위치 좌표 (y, x)와 벽을 부순 적이 있는 지를 나타내는 broke라는 변수를 넣어 현재 경로가 이전에 벽을 부쉈던 경로인지 파악해주었다.

 

broke가 0이면 현재 경로는 벽을 부순 적이 없는 경로이고, broke가 1이면 현재 경로는 벽을 한 번 부쉈던 경로라는 뜻이다.

 

이동하려는 곳이 0이면 broke가 0이든 1이든 이동할 수 있으므로 visited[][][broke]에 현재 visited[][][broke]에 1을 증가시켜 저장했고,

 

broke가 1인 상태에서는 0만 갈 수 있도록 해주었다.

 

코드

#include <bits/stdc++.h>
using namespace std;
// 상태를 차원으로 다루는 아이디어가 필요
bool board[1000][1000];
int visited[1000][1000][2];
// visited[][][0]: 벽을 부순 적 없는 상태에서의 이동 횟수 저장
// visited[][][1]: 벽을 한 번 부순 상태에서의 이동 횟수 저장
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M;
void BFS();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			if (s[j] == '1')
				board[i][j] = 1;
		}
	}
	BFS();
	if (!visited[N - 1][M - 1][0] && !visited[N - 1][M - 1][1])
		cout << -1;
}

void BFS() {
	queue<pair<pair<int, int>, int>> q;
	q.push({ {0,0},0 });
	visited[0][0][0] = 1;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int broke = q.front().second;
		// broke: 벽을 부순 적이 없으면 0, 있으면 1
		q.pop();
		if (y == N - 1 && x == M - 1) {
			cout << visited[y][x][broke];
			return;
		}
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i][0];
			int dx = x + dir[i][1];
			if (dy < 0 || dy >= N || dx < 0 || dx >= M)
				continue;
			if (visited[dy][dx][broke])
				continue;
			if (!board[dy][dx]) {
				// 0인 경우
				visited[dy][dx][broke] = visited[y][x][broke] + 1;
				q.push({ {dy,dx},broke });
			}
			else if (board[dy][dx] && !broke) {
				// 벽을 처음 부수는 경우
				visited[y][x][1] = visited[y][x][0];
				// 원래의 위치로 못 돌아가도록
				visited[dy][dx][1] = visited[y][x][0] + 1;
				q.push({ { dy,dx }, 1 });
			}
		}
	}
}

 

성능

코드 제출 결과