[백준/Python] 2206. 벽 부수고 이동하기

lemythe423·2023년 3월 15일
0

문제

최단거리를 구하는 문제라서 당연하게 bfs로 접근하는데 그냥 단순하게 생각하고 풀면 아래의 반례에서 틀리게 된다. bfs는 너비 우선 탐색으로 어떤 방향에서 접근하더라도 최단거리로 도착한 곳을 우선순위로 치게 된다. 이미 최단 거리로 돌아서 한 번 방문한 곳이라면 다시 방문하지는 않게 되는 것이다. 보통의 너비 우선 탐색 문제에서는 이게 통한다. 이미 최단 거리로 한 번 찍고 지나간 곳이라면 뒤늦게 그곳에 도달하는 경우는 이미 최단 거리가 아니게 되기 때문이다. 하지만 이 문제에서는 벽을 한 번 뚫고 지나갈 수 있다는 조건이 추가 되기 때문에 단순 너비 탐색으로는 이 문제를 풀 수 없게 된다.

6 4
0000
1110
0000
0111
1011
0000

위의 반례를 보면 (1, 2) 에 도달할 수 있는 경우가 2가지 존재한다.

  • (1, 1)에서 벽을 뚫고 지나오는 경우
  • 벽을 뚫지 않고 돌아서 오는 경우

bfs나 다익스트라를 적용해서 풀 경우 최단거리를 우선으로 치기 때문에 visit[1][2]에는 무조건 벽을 뚫고 지나온 경우가 기록되고 돌아서 온 경우는 이 기록을 뛰어넘는 단거리가 될 수 없다. 하지만 (1, 2)에서 끝까지 도달하기 위해서는 반드시 벽을 한 번 더 뚫어야만 한다 하지만 최단거리로 온 현재의 경우 이미 벽을 한 번 뚫었기 때문에 한 번 더 뚫을 수 없고 결국 도달할 수 없다는 결론이 나 -1을 리턴하게 된다. 하지만 벽을 뚫지 않고 돌아서 온 경우는 벽을 한 번 더 뚫을 수 있기 때문에 (1, 2)에 최단거리로 도착하지는 않았지만 최종적으로 도달 가능은 하다. 그렇다면 도달할 수 있는 최단거리가 존재하며 그것은 13으로 리턴되어야 한다.
즉, 어떤 위치에 도달했을 때 '벽을 이미 한 번 뚫고 지나온 경우'와 '벽을 뚫지 않고 지나온 경우' 두 가지 정보가 다 기록되어 있어야 한다. 최종적으로 어떤 쪽이 더 빠르게 도달할 지는 현재 위치까지의 정보가 아니라 앞으로 벽의 존재 유무 등의 이후의 조건에 달려있기 때문이다. 하지만 보통 bfs라면 현재 위치에 최단으로 도착했다면 끝까지도 최단으로 도착하게 되어있다.

참조

  • 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다. 구체적인 예시로는 다음과 같은 것들이 있습니다.
  1. 현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 할 것입니다.
  2. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능합니다

풀이1 (틀림)

  • 21%에서 틀렸습니다
import sys
from collections import deque
input = sys.stdin.readline

def bfs(i, j):
    queue.append((i, j, False))
    visit = [[0] * M for _ in range(N)]
    visit[i][j] = 1
    while queue:
        si, sj, flag = queue.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = si + di, sj + dj
            if -1 < ni < N and -1 < nj < M and not visit[ni][nj]:
                visit[ni][nj] = visit[si][sj] + 1
                if not arr[ni][nj]:
                    queue.append((ni, nj, flag))
                elif not flag and arr[ni][nj]:
                    queue.append((ni, nj, True))

    if (si, sj) == (N-1, M-1):
        return visit[si][sj]
    return -1

N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
queue = deque()
print(bfs(0, 0))

풀이2 (dfs/Recursion Error)

  • 답은 나오지만 백준에선 런타임 에러
import sys
from collections import deque
input = sys.stdin.readline

def dfs(y, x, cnt, flag):
    global res
    if res < cnt:
        return

    if (x, y) == (M-1, N-1):
        res = cnt
        return 
    
    for dx, dy in ((0, 1), (1, 0), (-1, 0), (1, 0)):
        nx, ny = x + dx, y + dy
        if -1 < nx < M and -1 < ny < N and visit[ny][nx] == 0:
            visit[ny][nx] = 1
            if arr[ny][nx] and not flag:
                dfs(ny, nx, cnt+1, True)
            elif arr[ny][nx] == 0:
                dfs(ny, nx, cnt+1, flag)
            visit[ny][nx] = 0

N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
visit = [[0] * M for _ in range(N)]
# stack = deque()
res = 1e9

dfs(0, 0, 1, False)
if res == 1e9:
    res = -1
print(res)

풀이3 (최종 통과)

  • r, c가 N-1, M-1인 걸 델타를 돌리면서 확인하면 훨씬 빨리 끝날 거 같지만

    1 1
    0

이라는 반례 때문에 100%에서 에러 뜬다

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
visit = [[[0, 0] for _ in range(M)] for _ in range(N)]
queue = deque([(0, 0, 0)])
res = -1

while queue:
    r, c, wall = queue.popleft()
    if (r, c) == (N-1, M-1):
        res = visit[r][c][wall] + 1
        break

    for dr, dc in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if -1 < nr < N and -1 < nc < M and not visit[nr][nc][wall]:    
            if not wall and arr[nr][nc]:
                visit[nr][nc][1] = visit[r][c][wall] + 1
                queue.append((nr, nc, 1))
            elif not arr[nr][nc]:
                visit[nr][nc][wall] = visit[r][c][wall] + 1
                queue.append((nr, nc, wall))
print(res)
profile
또나만좋아하지이거

0개의 댓글