[백준] 2206번 벽 부수고 이동하기 (파이썬)

< 백준 2206번 벽 부수고 이동하기 - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 해당 문제를 보고 처음 생각한 것은 완전 탐색을 통해 벽을 찾고 모든 벽을 0으로 바꾸고 BFS 진행하는 것을 반복하는 방식을 생각했다.
• 이 경우, BFS가 노드의 개수 만큼 시간복잡도를 가져서 O(NM)의 복잡도를 가지고 N, M 둘다 최대 1000이다. 그리고 벽의 개수 또한 최대 O(NM) 이기에 시간 복잡도가 최악의 경우 1000^4가 나와서 2초 안에 풀 수 없다.
• 다른 경우를 생각해야할 것 같다. 일단 우리가 원하는 구현은 시작점에서 목표점으로 가는데 벽을 최대 1개 부수고의 최단 거리를 찾는 것이다. 그렇다면 존재하는 모든 벽을 부술 필요가 있을까? 없다. 내가 가는 경로에서 유의미한 벽들만을 부수면 된다.
• 먼저 알아야할 것은 모든 최단 거리 알고리즘에서 예를 들어 BFS, 다익스트라, 플루이드 워셜 등등에서 최단 거리를 저장하는 배열을 가진다. dist[x]=10 이런 식으로 거기엔 최단 거리의 값을 저장한다. 근데 내가 어떤 상태를 넣고 싶다. 예를 들어서 부순 벽의 개수를 넣는다고 하면 dist[x]=(10, 3) 이런 식으로 저장하면 될까? 안된다. 그 이유는 어떤 식으로라도 반례가 생긴다고 한다. 그도 그럴 것이 그 개수에 따라 생각해야할 조건들이 너무너무 많아질 것같다. 그래서 상태는 차원으로 표현을 한다고 한다. 사실 dist[x]에서 x도 상태이다. 시작점에서 x 인덱스까지 상태가 변한 것이다. 거기에 부순 벽의 개수까지 넣어서 dist[x][wall] = 10 이런 식으로 상태를 표현해야 반례가 생기지 않는다.
• 그렇다면 해당 그래프에서 차원을 하나 더 만들어서 거리를 계산해야 한다는 것이다. 그래서 벽을 부순 경우 ( 1 ) 과 벽을 부수지 않은 경우 ( 0 )으로 표현을 하겠다.
• 이젠 벽이 없는 인덱스에서 벽이 없는 인덱스로 가는 경우를 생각해보자. 이전 인덱스에서 벽을 부숴서 해당 인덱스로 왔을 수도 있고 벽을 안부수고 왔을수도 있다. 그래서 벽을 부순 경우도 처리하고 벽을 부수지 않은 경우도 처리한다.
• 벽이 있는 인덱스에서 벽이 없는 인덱스로 가는 경우, 이 경우 벽을 부수지 않은 경우는 없다. 벽이 있던 곳에서 왔기 때문이다.
• 벽이 없는 인덳스에서 벽이 있는 인덱스로 가는 경우, 벽을 안부수고는 가지 못한다.
• 이것들을 생각해서 코드로 짜보자.

코드구현

from collections import deque
def solution():
    q = deque()
    q.append((0, 0, 0))
    visited = [[[-1]*2 for _ in range(M)] for _ in range(N)] # 벽의 부숨 유무도 표현한 3차원 그래프이다.
    visited[0][0][0] = 1 # 맨처음 인덱스는 무조건 벽을 부수지 않았기에 벽을 부순 1에는 값을 삽입하지 않는다.
    while q:
        r, c, state = q.popleft() # 상태까지 큐에 삽입하는 이유는 인덱스가 같아도 상태가 다르면 큐에 들어온다.
        # 어떻게 보면 인덱스가 다른 경우인것이다. state가 다른 것은.
        for i in range(4): # 인접 노드를 확인한다.
            nr, nc = r + dx[i], c + dy[i] 
            if not(0<=nr<N and 0<=nc<M):
                continue
            if visited[nr][nc][state] != -1: # 만약 인접노드에 같은 스테이트가 -1이 아니면 이미 최단 거리를 구한 것이다.
            # 그럼 0에서 -1로 가는 경우를 두 개의 노드에서 같은 벽을 넣으려고 하면 어떻게 하는가? 이 경우도 넘어간다.
                continue
            if graph[nr][nc] == 0: # 다음 노드가 벽이 아닌 경우
                visited[nr][nc][state] = visited[r][c][state] + 1 # 벽을 부순 상태는 그 상태로 쭉 연결되어야하고 아닌 상태는 그 상태로 쭉 연결되어야한다.
                q.append((nr, nc, state))
            else: # 다음 노드가 벽인 경우
                if state == 0: # 현재 노드가 벽이 아닌 경우만 가능하다. 벽 - 벽은 이동불가능하다.
                    visited[nr][nc][not state] = visited[r][c][state] + 1 # 벽을 부수지 않은 상태에서 벽을 부순 상태로의 연결을 나타낸다.
                    q.append((nr, nc, not state))
    print(min(visited[N-1][M-1][0], visited[N-1][M-1][1]) if visited[N-1][M-1][0] != -1 and visited[N-1][M-1][1] != -1 else visited[N-1][M-1][1]+visited[N-1][M-1][0]+1)
if __name__ == "__main__":
    dx = (0, 1, 0, -1)
    dy = (1, 0, -1, 0)
    N, M = map(int, input().split())
    graph = [list(map(int, input())) for _ in range(N)]
    solution()