백준 알고리즘 2206 (벽 부수고 이동하기) - C++, Python

[문제] 백준 알고리즘 2206 (벽 부수고 이동하기)

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

2206번: 벽 부수고 이동하기

N x M 미로 탐색(2178번)처럼 최단 거리 찾는 문제인데,  벽을 하나 부수고 갈 수 있는 기회가 있다. 

> https://wlstyql.tistory.com/91

백준 알고리즘 2178 (미로 탐색) - C++, Python

 

[문제 해결] 

 

1. BFS를 위해 Queue, visited, while q 사용

    - visited를 3차원(N x M x 2)으로 만들어서 벽을 부수지 않고 이동할 때와

      벽을 부순 후의 이동으로 차원을 나누어서 계산한다. (간섭이 생김)

    - visited를 쓰던 순으로 구현하면 Python에선 2 x N x M 주의!

2. c(chance)라는 변수를 통해 벽을 부수기 전/후의 차원을 나누어 사용.

    - 일반적일 때는 미로 찾기를 진행

    - 벽이면서 부수기 찬스가 있을 때는, 찬스를 사용하고 사용한 차원으로 이동.

3. 시작과 도착도 세어준다는 점, 갈 수 없으면 -1을 고려하며 BFS 진행. 

 

 

[C++]

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct INFO {
	int x, y, c; // c: break chance
};

const int MAX = 1001;
int n, m;
bool map[MAX][MAX];
int visited[MAX][MAX][2];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int solve_bfs() {
	queue<INFO> q;
	q.push({ 0, 0, 0 });
	visited[0][0][0] = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int c = q.front().c; // 0 벽 뚫고나면 1
		q.pop();
		if (x == n - 1 && y == m - 1) {
			return visited[x][y][c];
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (!visited[nx][ny]) {
					if (!map[nx][ny]) {
						visited[nx][ny][c] = visited[x][y][c] + 1;
						q.push({ nx, ny, c });
					}
					else if (map[nx][ny] && !c) { // 벽 뚫기
						visited[nx][ny][1] = visited[x][y][c] + 1;
						q.push({ nx, ny, 1 }); // 1 뚫음 표시
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	memset(map, 0, sizeof(map));
	memset(visited, 0, sizeof(visited));
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	printf("%d\n", solve_bfs());
	return 0;
}

 

[Python]

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[[0] * m for _ in range(n)] for _ in range(2)]
q = deque()
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)

def solve_bfs():
    q.append((0, 0, 0))  # x, y, c(chance)
    visited[0][0][0] = 1  # c, x, y
    while q:
        x, y, c = q.popleft()
        if x == n-1 and y == m-1:
            return visited[c][x][y]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not visited[c][nx][ny]:
                    if not board[nx][ny]:
                        visited[c][nx][ny] = visited[c][x][y] + 1
                        q.append((nx, ny, c))
                    elif board[nx][ny] and not c:
                        visited[1][nx][ny] = visited[c][x][y] + 1
                        q.append((nx, ny, 1))
    return -1

print(solve_bfs())