[백준(Baekjoon)] 2206 벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

예제를 보시려면 더보기를 누르세요.

예제 입력 1 

6 4
0100
1110
1000
0000
0111
0000

 

예제 출력 1

15

 

예제 입력 2 

4 4
0111
1111
1111
1110

예제 출력 2 

-1

 

 

---

 나의 코드

[Python(파이썬)]

def bfs():
    q = deque()  # 시작 좌표
    q.append((0, 0, 0, 1))  # x좌표, y좌표, 벽 부순 여부, 이동 횟수
    check[0][0] = [1, 0]  # 시작 좌표 노드 방문 표시

    while q:  # 큐가 빌 때까지
        x, y, bcnt, result = q.popleft()
        if x == n - 1 and y == m - 1:  # 마지막 지점에 도착하면 break
            return result

        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:   # 상하좌우 이동
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if check[nx][ny][0] == 0 or check[nx][ny][1] > bcnt:
                    if graph[nx][ny] == 0:  # 길이 있는 경우
                        check[nx][ny] = [1, bcnt]
                        q.append((nx, ny, bcnt, result+1))
                    elif bcnt == 0:     # 길은 없지만 한번도 벽을 부순적 없는 경우
                        check[nx][ny] = [1, bcnt+1]
                        q.append((nx, ny, bcnt+1, result+1))

    return -1

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]
check = [[[0, 0] for _ in range(m)] for _ in range(n)]  # [방문여부, 벽을 부쉈는지 여부]
print(bfs())

---

코드 풀이

 이동 경로를 구하다가 갑자기 벽을 부수라니,,, 처음에는 너무 어렵게 생각했다. 

이것 저것 생각하다가 결국 이동 경로 구하는 문제와 다른 점은 이동경로 구하지만 '벽을 부수고 간다. 부수지 않고 간다.' 두 조건으로 따로 이동하면 될 일이다. 라는 것을 생각했다. 

 

 

처음 코드 -> 틀린 코드

def bfs():
    q = deque()  # 시작 좌표
    q.append((0, 0, 0, 1))
    visited[0][0] = 1  # 시작 좌표 노드 방문 표시
    cnt = 0

    while q:  # 큐가 빌 때까지
        x, y, bcnt, result = q.popleft()
        if x == n - 1 and y == m - 1:  # 마지막 지점에 도착하면 break
            cnt += 1
            print(result)
            break

        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny, bcnt, result+1))
                elif bcnt == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny, bcnt+1, result+1))

    if cnt == 0:
        print(-1)


import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

visited = [[0]*m for _ in range(n)]
bfs()

 

처음에는 위와 같이 구현을 했는데 예제가 통과가 되길래 맞겠다 하고 제출을 했는데 '틀렸습니다'가 나왔다. 

이유를 찾기 위해 통과 되지 않는 예제를 가지고 큐에 들어오는 순서 출력을 찍어서 확인해보았다. 

 

 

지도의 일부라고 생각해 보자

 (0, 0)에서 (1, 1)로 이동방법은 다음과 같이 두가지가 있다. 

똑같이 3번 이동하는데 한 가지 경우는 벽을 부수고 이동하고 다른 한 가지 경우는 벽을 부수지 않고 이동하는 경우이다. 

 

그럼 문제가 제대로 구현되려면 아래와 같이 작동되어야 한다. 

(0, 0) 좌표에서 queue에

1) (1, 0, 1, 2) 와 (0, 1, 0, 2)가 모두 담긴다. 

2) 큐의 첫번째 (1, 0, 1, 2)를 pop한 다음 해당좌표에서의 이동인 (1, 1, 1, 3)을 담는다. 

3) 큐의 첫번째 (0, 1, 0, 2)를 pop한 다음 해당좌표에서의 이동인 (1, 1, 0, 3)을 담는다. 

 

 

하지만 문제는 여기서 발생했다. 

벽을 부수는 이동인 (1, 0)에서 (1, 1)을 방문했을 때 이미 (1, 1)의 방문여부 좌표에는 1로 바꼈던것!!

그래서 벽을 부수지 않고 이동하는 (0, 1)에서 (1, 1)를 방문하고 싶은데 visited[nx][ny] == 0이 아니다 보니  (1, 1, 0, 3)를 큐에 삽입하지 못하는 것이었다. 

그러니 이동이 제대로 될리가 없었다. 

 

 

변경 1 : 3차원 리스트

 

방문여부 리스트를 2차원으로 구현하지 않고 3차원으로 구현했다. 

# 원래 BFS 방문 여부 리스트
check = [[0]*m for _ in range(n)]

# 벽부수기 방문 여부 리스트
check = [[[0, 0] for _ in range(m)] for _ in range(n)]  # [방문여부, 벽을 부쉈는지 여부]

 

변경 2 : check[nx][ny][1] > bcnt

 

        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:   # 상하좌우 이동
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if check[nx][ny][0] == 0 or check[nx][ny][1] > bcnt:
                    if graph[nx][ny] == 0:  # 길이 있는 경우
                        check[nx][ny] = [1, bcnt]
                        q.append((nx, ny, bcnt, result+1))
                    elif bcnt == 0:     # 길은 없지만 한번도 벽을 부순적 없는 경우
                        check[nx][ny] = [1, bcnt+1]
                        q.append((nx, ny, bcnt+1, result+1))

 

큐에 넣기 위해서는 첫번째로 
1) 0 <= nx < n and 0 <= ny < m (좌표안에 있는지 여부 확인)
2) check[nx][ny][0] == 0 (방문하지 않은 좌표인지 확인) or check[nx][ny][1] > bcnt (이전에는 벽을 부수고 왔지만 현재는 벽을 부수지 않고 왔는가 확인)

위의 두가지가 통과 됐다면 
3) graph[nx][ny] == 0 (벽이 있는지 없는지 확인)
3-1) 벽이 없다면 q.append((nx, ny, bcnt, result+1)) -> 그냥 이동
3-2) 벽이 있다면 (bcnt == 0) 벽을 부순적 있는지 없는지 확인
3-2-1) 벽을 부순적 있다면 pass
3-2-2) 벽을 부순적 없다면 q.append((nx, ny, bcnt+1, result+1)) -> 벽을 부수고 이동

 

 그렇다면  check[nx][ny][1] > bcnt 에 대해서 좀 더 생각해보자 

 

 

낙서 끄적인 수준이지만 그냥 벽을 부순애가 먼저 들어와서 queue안에 들어가고 난 후에도 벽을 안부순애가 그 위치에 방문한다면 queue에 들어갈 수 있게 해준 코드라는 의미 :)

---

문제 출처

2206번: 벽 부수고 이동하기