[BOJ] Python 백준 2206번 벽 부수고 이동하기 골드 4

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

2206번: 벽 부수고 이동하기

문제 풀이

---

전형적으로 시작 노드에서 도착 노드까지 장애물을 피해 도착하는 최단 거리를 출력하는 문제이다.

 

다만 다소 어렵게 느껴질 수 있는 부분은 기존의 그래프 탐색은 방문 가능한 노드인지(장애물이 아닌지), 방문한 노드인지를 체크하고 탐색하지만, 이 문제에선 최대 한 개의 벽을 부수고 이동할 수 있다는 개념이다.

 

아마 정답 비율이 낮은 이유(약 23%)는 이 개념 때문이지 않을까 추측해본다.

 

이 문제에서는 살짝 다르게 생각하는 방법이 필요하다.

 

물론 문제대로 매번 현재 상태가 벽을 부수고 이동한 상태인지 아닌지 기록할 수도 있겠지만 3차원 리스트로 생각하면 좀 더 이해하기 쉬울 것이다.

 

즉, 기존의 2차원 리스트를 2개 갖는 3차원 리스트로 생각하고 벽을 부수지 않은 상태라면 0번째 인덱스의 2차원 리스트, 벽을 부순 상태라면 1번째 인덱스의 2차원 리스트로 생각하면 된다.

 

벽을 부수는 것을 한 층 올라간다고 생각하면 이해가 쉬울 것이다.

 

이렇게 개념만 잡고 간다면 나머지는 기존의 2차원 리스트에서 최단 거리를 찾는 알고리즘과 같기 때문에 어렵지 않게 구현할 수 있을 것이다.

 

전체 코드를 따라가면서 이해하면 도움 될 것이다.

 

 

import sys
from collections import deque

#위,오른,아래,왼
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
graph=[]
res=-1
queue=deque()
for i in range(n):
    graph.append(list(map(int,list(sys.stdin.readline().rstrip()))))
visited=[[[0 for i in range(m)] for j in range(n)]for k in range(2)]

       #벽 부수기 전,시작위치,거리
queue.append([0,0,0,1])
visited[0][0][0]=1
while len(queue)>0:
    temp_list=queue.popleft()
    for i in range(4):
        x=temp_list[1]+dx[i]
        y=temp_list[2]+dy[i]
        if 0<=x<n and 0<=y<m:
            if x==n-1 and y==m-1:
                res=temp_list[3]+1
                break
            elif graph[x][y]==0 and visited[temp_list[0]][x][y]==0:
                visited[temp_list[0]][x][y]=1
                queue.append([temp_list[0],x,y,temp_list[3]+1])
            elif graph[x][y]==1:
                if temp_list[0]==0 and visited[0][x][y]==0:
                    visited[1][x][y]=1
                    queue.append([temp_list[0]+1,x,y,temp_list[3]+1])

    if res!=-1:
        break
if n==1 and m==1:
    print(1)
else:
    print(res)

 

먼저 최대 1000000개의 노드가 가능한 그래프이고 3차원 리스트로 생각하므로 최대 2000000개가 가능하기에 최대한 시간을 줄일 필요성이 있었다.

 

따라서 sys 모듈을 이용하여 입력 시간을 줄였고 시작과 끝부분에서 데이터 삽입 삭제가 가능한 deque 모듈을 사용하여 BFS에서 최대한 시간을 줄이려고 노력했다.

 

그냥 List에서 BFS를 위해 pop(0)을 한다면 매번 O(n)의 시간 복잡도가 걸리기 때문이다.

 

5, 6번째 줄에선 한 노드를 기준으로 0번째 인덱스부터 차례대로 위 노드, 오른쪽 노드, 아래 노드, 왼쪽 노드로 가능한 방향을 저장한 리스트이다.

 

10번째 줄은 BFS 탐색을 위해 데크로 선언하였다.

 

11번째 줄에선 그래프로 저장하며 13번째 줄의 visited 리스트는 각 각 방문한 노드인지 체크하는 리스트인데 중요한 것은 3차원 리스트로 선언한 것이다.

 

최대 한 번 벽을 부수고 이동할 수 있기 때문에 2개의 2차원 리스트로 선언했고 만약 2번 3번 벽을 부수고 이동한다면 각 층을 올라간다고 생각하여 3개, 4개의 2차원 리스트로 선언하면 된다.

 

16번째 줄에서 데크에 넣은 리스트는 벽을 부수기 전, 시작 위치, 거리이다.

 

그러고 나서 18번째 줄에서 BFS를 실행하면 된다.

 

19번째 줄의 popleft()는 O(1)의 시간 복잡도가 걸리고 24번째 줄에선 도착하면 res를 갱신한 뒤 BFS를 탈출한다.

 

27번째 줄은 방문 가능한 노드일 경우 데크에 넣는 코드고 30번째 줄은 벽이 있을 때 부수고 온 상태가 아니라면 벽을 부수고(층을 이동하여) 노드를 데크에 넣어준다.

 

마지막으로 res를 출력하면 통과할 수 있다.

 

결과 화면

 

알고리즘 구현 자체는 다른 그래프 탐색과 비슷한 수준이지만 벽을 부수고 이동할 수 있다는 조건 때문에 어렵게 다가왔다.

 

주어진 조건을 이해와 구현이 쉬운 방법으로 변환하는 게 핵심 포인트이며 이처럼 다차원 리스트로 변환하여 생각하는 방법은 은근히 나오니 꼭 익숙해지는 게 좋을 것 같다.

 

비슷하게 다차원 리스트를 이용하는 문제를 추천하며 마무리 짓도록 하겠다.

 

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

7569번: 토마토