백준 2206 벽 부수고 이동하기 Python 3

 

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

2206번: 벽 부수고 이동하기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2206.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque

def move():
    q = deque([[0, 0, 1, 0]])
    visit = [[[0]*M for _ in range(N)] for _ in range(2)]
    visit[0][0][0] = 1
    while q:
        x, y, cnt, broken = q.popleft()
        if x == M-1 and y == N-1:
            print(cnt)
            return
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            if 0 <= nx < M and 0 <= ny < N:
                if not visit[broken][ny][nx]:
                    if _map[ny][nx] == '0':
                        q.append([nx, ny, cnt+1, broken])
                        visit[broken][ny][nx] = 1
                    elif not broken:
                        q.append([nx, ny, cnt+1, 1])
                        visit[1][ny][nx] = 1
    print(-1)

input = sys.stdin.readline
N, M = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
_map = list()
for _ in range(N):
    _map.append(list(input().rstrip()))

move()

---

풀이 과정

풀이 시간 43분

(1, 1)에서 (M, N)으로 도착하기 위해 지나간 칸의 최소를 구해야 하는 문제다.

이때, 벽이 있는 칸으로는 움직일 수 없는데, 단, 하나의 경로에서 최대 벽 하나는 깨고 이동할 수 있다.

벽 깨기를 어떻게 처리할지가 관건인 문제이다.

 

처음에는 큐에 [현재 위치(x, y), 지나온 칸 수, 벽을 깼는지 안깼는지의 여부]를 넣고, 2차원 visit으로 방문처리 하였다.

그리고 탐색하면서 인접한 칸에 벽이 없다면 방문처리 후 큐에 담고, 벽이 있다면 이전에 벽을 깬적이 없다면 깨고 해당 칸을 방문처리 후 큐에 담아주었다.

하지만 결과는 틀렸습니다.가 나왔고, 3차원 visit을 사용해서 문제를 해결할 수 있었다. (반례는 아래 오답노트에 적어두겠다.)

visit[broken][y][x]로 방문처리하고 탐색해야 다른 루트에서 먼저 벽을 깨고 방문처리한 예외까지 커버하여 모든 경우를 탐색할 수 있다.

import sys
from collections import deque

def move():
    q = deque([[0, 0, 1, 0]])
    visit = [[[0]*M for _ in range(N)] for _ in range(2)]
    visit[0][0][0] = 1
    while q:
        x, y, cnt, broken = q.popleft()
        if x == M-1 and y == N-1:
            print(cnt)
            return
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            if 0 <= nx < M and 0 <= ny < N:
                if not visit[broken][ny][nx]:
                    if _map[ny][nx] == '0':
                        q.append([nx, ny, cnt+1, broken])
                        visit[broken][ny][nx] = 1
                    elif not broken:
                        q.append([nx, ny, cnt+1, 1])
                        visit[1][ny][nx] = 1
    print(-1)

input = sys.stdin.readline
N, M = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
_map = list()
for _ in range(N):
    _map.append(list(input().rstrip()))

move()

---

 

오답 노트

이렇게 2차원 배열로 visit 처리를 해주면, 커버할 수 없는 예외가 발생한다.

5 4
0001
1101
0001
0111
0010

#answer = 12

아래 코드로 돌리면 -1이 나온다.

이유는 BFS는 너비를 우선적으로 탐색하기 때문에 최단거리 찾기에 사용되는데, 이전에 벽을 허물고 먼저 도착한 칸이 있다면 이미 방문처리가 되어서 탐색이 이뤄지지 않기 때문이다.

따라서 3차원 visit을 활용해서 벽을 깼는지의 여부에 따라 탐색하고 방문처리 해야 한다.

import sys
from collections import deque

def move():
    q = deque([[0, 0, 1, 0]])
    visit = [[0]*M for _ in range(N)]
    visit[0][0] = 1
    while q:
        x, y, cnt, broken = q.popleft()
        if x == M-1 and y == N-1:
            print(cnt)
            return
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            if 0 <= nx < M and 0 <= ny < N and not visit[ny][nx]:
                if _map[ny][nx] == '0':
                    q.append([nx, ny, cnt+1, broken])
                    visit[ny][nx] = 1
                elif not broken:
                    q.append([nx, ny, cnt+1, 1])
                    visit[ny][nx] = 1
    print(-1)

input = sys.stdin.readline
N, M = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
_map = list()
for _ in range(N):
    _map.append(list(input().rstrip()))

move()