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

1. 조건

- 0 : 이동 가능 / 1 : 이동 불가능

- (1,1) → (N,M) 으로 이동

- 한개까지 벽 부시기 가능

- (1,1), (N,M)은 항상 0

 

2. 입력

- 가로 : M, 세로 : N

 

3. 출력

- 최단거리 출력하되 불가능하면 -1

 

4. 경계값 반례

1 1
1
// 1

1 1
0
// 1

3 4
0111
1000
0000
// 6

3 4
0111
0000
0000
// 6

 

5. 풀이

- 0층은 벽을 안 부쉈을 때, 1층은 벽을 한개 부쉈을 때로 가정해 [2][MAX_NUM][MAX_NUM] 배열을 만든다.

- (0,0)은 무조건 0이므로 0층 [0][0]에서 탐색을 시작한다.

- (N-1, M-1)까지 도달할 수 있는 조건은 3가지이다.

ㄴ 1) 벽을 한번도 안 부쉈고 가야할 곳도 벽이 없음

ㄴ 2) 벽을 한번도 안 부쉈고 가야할 곳에 벽이 있음

ㄴ 3) 벽을 한번 부쉈고 가야할 곳에 벽이 없음

ㄴ 4) 이 외 케이스는 못 간다

- 위의 3가지 조건을 이용하여 BFS 탐색을 돌린다.

 

---

 

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 1002
using namespace std;

char arr[MAX_NUM][MAX_NUM];
int visited[2][MAX_NUM][MAX_NUM];	// 0 : 벽 안 부심, 1 : 벽 부심
queue<pair<char, pair<int, int>>> q;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n;
int m;

void bfs() {
	while (!q.empty()) {
		char floor = q.front().first;	// 벽 부쉈나 안 부쉈나
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

			// 그동안 벽을 안 부쉈고 계속 안 부심
			if (floor == '0' && arr[nx][ny] == '0' && visited[0][nx][ny] == 0) {
				visited[0][nx][ny] = visited[0][x][y] + 1;
				q.push({ '0', {nx, ny} });
			}
			// 그동안 벽을 안 부쉈고 벽을 만남
			else if (floor == '0' && arr[nx][ny] == '1' && visited[1][nx][ny] == 0) {
				visited[1][nx][ny] = visited[0][x][y] + 1;
				q.push({ '1', {nx,ny} });
			}
			// 벽을 한번 만났고 앞으로는 안 만남
			else if (floor == '1' && arr[nx][ny] == '0' && visited[1][nx][ny] == 0) {
				visited[1][nx][ny] = visited[1][x][y] + 1;
				q.push({ '1', {nx,ny} });
			}
			// 어차피 그 외 케이스는 의미없음
		}
	}
}

int CheckAnswer() {
	if (visited[0][n - 1][m - 1] == 0 && visited[1][n - 1][m - 1] == 0)
		return -1;
	else if (visited[0][n - 1][m - 1] != 0 && visited[1][n - 1][m - 1] != 0)
		return min(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1]);
	else
		return max(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1]);
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	visited[0][0][0] = 1;
	q.push({ '0', { 0,0 } });
	bfs();

	cout << CheckAnswer();

	return 0;
}

 

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

n, m = map(int, read().rstrip().split())

arr = [[] * m for _ in range(n)]
visited = []
for _ in range(2):
    visited.append(list([0] * m for _ in range(n)))

for i in range(n):
    arr[i] = list(read().rstrip())

def bfs():
    while q:
        isBroken, x, y = q.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 벽을 한번도 안 부쉈고 앞으로도 안 부심
            if not isBroken and arr[nx][ny] == '0' and visited[0][nx][ny] == 0:
                visited[0][nx][ny] = visited[0][x][y] + 1
                q.append((False, nx, ny))
            # 벽을 한번도 안 부쉈고 하나 부숴야함
            elif not isBroken and arr[nx][ny] == '1' and visited[1][nx][ny] == 0:
                visited[1][nx][ny] = visited[0][x][y] + 1
                q.append((True, nx, ny))
            # 벽을 한번 부쉈고 앞으로는 안 부심
            elif isBroken and arr[nx][ny] == '0' and visited[1][nx][ny] == 0:
                visited[1][nx][ny] = visited[1][x][y] + 1
                q.append((True, nx, ny))
 
def CheckAnswer():
    if visited[0][n-1][m-1] == 0 and visited[1][n-1][m-1] == 0:
        return -1
    elif visited[0][n-1][m-1] != 0 and visited[1][n-1][m-1] != 0:
        return min(visited[0][n-1][m-1], visited[1][n-1][m-1])
    else:
        return max(visited[0][n-1][m-1], visited[1][n-1][m-1])

visited[0][0][0] = 1
q.append((False, 0, 0))

bfs()

print(CheckAnswer())