[백준] 2206번: 벽 부수고 이동하기(그래프, Python)

문제 링크

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

2206번: 벽 부수고 이동하기

 

문제 풀이

풀이 설명

• 분류: 그래프 이론, 그래프 탐색, 구현

 이동 중 벽을 만났을 때 부수고 가야할지 말아야할지, 어떤게 최적인지 현재 좌표에서 어떻게 알 수 있는지를 고민하다가 결국 풀이를 참고했다. 

이런 경우엔 그래프 탐색에서 많이 사용하는 방법이라고 한다. (질문 게시판에 너무 좋은 글이 있다.)

-> 모든 벽을 한번 부수고 다 탐색하는 완전탐색을 하기엔 시간초과인 경우

-> BFS로 탐색하되 큐에 현재 상태를 같이 넣는 것이다. 

무슨 말이냐면 현재 좌표에 도달했을 때 벽을 부시고 온 자리인지 아닌지를 확인하는 것이다. (벽은 1개만 부술 수 있기 때문에,,,)

[질문게시판 중요 부분 참고]

1. (스포일러) 그래서 이 문제에서는 BFS에 대해 새로운 테크닉을 요구합니다. 단순히 좌표만을 큐에 넣어 탐색하는 방식을 넘어, "현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고, 각각을 별개로 방문 체크해줘야 하는 문제입니다. visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 합니다.
2. 이 문제에서는 같은 칸에 방문하는 경우 벽을 안 부순 것이 더 유리하기 때문에 벽을 부쉈는지 여부를 방문 배열에 기록하여 부순 횟수가 더 적을 때만 방문하는 방법도 됩니다. 그러나 이는 문제의 특성 때문에 이 문제에서만 통하는 그리디이므로 다른 문제에도 함부로 사용해서는 안 됩니다.

간략한 코드 설명

• visited[wall][x][y], wall -> 0: 벽 부수기 전, 1: 벽 없앰
  • ex. visited[1][x][y] == True -> 벽을 부시고 (x, y) 좌표에 도달한 상태
  • visited[1][x][y] == False -> 벽을 안부시고 (x, y) 좌표에 도달함
• 다른 상황과 동일하게 방문 여부를 묻는 visited는 배열은 3차원 False 배열로 채운다. (시작 좌표 제외하고)
• dist: 거리배열 2차원, 시작부분부터 칸마다의 최단 거리를 기록하는 배열
• 벽을 만난 경우 - 해당 좌표에 방문 했는지 & 이전에 벽을 부순 적이 있는지(벽은 원래 못가는 좌표)
• 벽이 아닌 경우 - 해당 좌표를 방문 했는지만 확인 -> 큐에 삽입
• N-1, M-1 좌표에 다다른 거리들에서 최소값을 뽑아 최단 거리로 출력한다. 
• (예외처리)
• (N, M) == (1, 1) 인 경우, 시작과 도착 자리는 언제나 빈칸 이므로 거리는 1이다.

코드

'''
* visit[x][y][wall]
* visit[x][y][0] : 벽을 부수지 않고 좌표(x, y)를 방문
* visit[x][y][1] : 벽을 부수고 좌표(x, y)를 방문
'''
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
# input 지도
maps = []
for _ in range(N):
    maps.append(list(map(int, input().rstrip())))

if (N, M) == (1, 1):
    print(1)
else:

    # 방문 여부 & 벽 부순 여부로 3차원 배열 생성
    visited = [[[False] * M for _ in range(N)] for _ in range(2)]
    dist = [[0] * M for _ in range(N)]

    q = deque([(0, 0, 0)])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # - 이동의 조건:
    # - 벽인 경우, 방문한적 없고 & 벽 부순적 없음(벽이면 원래 못 감)
    # - 벽이 아닌 경우, 방문한적 없음
    visited[0][0][0], visited[1][0][0] = True, True
    dist[0][0] = 1
    dist[N-1][M-1] = -1 # 방문하지 않았을 때의 default
    flag = 0
    temp = []
    while q:
        x, y, wall = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            flag = 0

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            # 벽인 경우 -> 현재 좌표까지 벽을 부순 적이 없고, 다음 상태에 방문한 적이 없는 경우,
            if maps[nx][ny] == 1 and wall == 0 and not visited[wall + 1][nx][ny]:
                visited[wall+1][nx][ny] = True
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny, wall+1))

            # 벽이 아닌 경우, 방문 여부만 중요
            if maps[nx][ny] == 0 and not visited[wall][nx][ny]:
                visited[wall][nx][ny] = True
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny, wall))

            if (nx, ny) == (N-1, M-1):
                temp.append(dist[nx][ny])

    result = 0
    if visited[0][N-1][M-1] or visited[1][N-1][M-1]: # n-1, m-1 에 방문 했다면
        dist[N-1][M-1] = min(temp)

    print(dist[N-1][M-1])