백준 16933 [벽 부수고 이동하기 3] 파이썬

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

 

처음으로 골드1 문제를 풀었다... ㅠㅠ

이전에 풀었던 문제, 그리고 전에 풀었던 문제들이 도움이 되었다.

마찬가지로, 3차원 만들고 벽 부수는 경우와 그렇지 않은 경우에 대하여 탐색하면 되나, 제자리에 머무르는 경우도 있기 때문에 visit을 더하지 않고, 큐에 따로 이동횟수를 더하는 방식으로 진행하였다.

import sys
from collections import deque

# 방향 벡터 (우, 좌, 상, 하)
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]

# 입력 받기 (N: 행, M: 열, K: 부술 수 있는 벽 개수)
N, M, K = map(int, sys.stdin.readline().split())

# 지도 정보 저장
field = []
for _ in range(N):
    field.append(list(map(int, sys.stdin.readline().rstrip())))

# 방문 여부 체크 (visited[r][c][k]: (r,c) 위치에서 k번 벽을 부술 수 있을 때 방문 여부)
visited = [[[0 for _ in range(K+1)] for _ in range(M)] for _ in range(N)]

def search(map, visit):
    success_flg = False  # 도착 여부 플래그
    q = deque()

    # (0,0)에서 시작, K개의 벽을 부술 수 있음, 이동 횟수는 1, 낮 상태로 시작
    q.append((0, 0, K, 1, True))
    visit[0][0][K] = 1  # (0,0)에서 벽을 K개 남긴 상태로 방문 표시

    while q:
        r, c, k, cnt, is_day = q.popleft()

        # 도착 지점에 도달하면 이동 횟수 출력 후 종료
        if r == N-1 and c == M-1:
            print(cnt)
            success_flg = True
            break

        # 4방향 탐색
        for i in range(4):
            R, C = r + dr[i], c + dc[i]

            # 맵 범위 내에 있는지 확인
            if 0 <= R < N and 0 <= C < M:
                # 벽이 없는 경우 (이동 가능)
                if map[R][C] == 0 and visit[R][C][k] == 0:
                    visit[R][C][k] = visit[r][c][k] + 1  # 방문 표시
                    q.append((R, C, k, cnt + 1, not is_day))  # 낮/밤 변경 후 큐에 추가

                # 낮일 때 벽을 부술 수 있는 경우
                if is_day:
                    if map[R][C] == 1 and k > 0 and visit[R][C][k-1] == 0:
                        visit[R][C][k-1] = visit[r][c][k] + 1  # 방문 표시
                        q.append((R, C, k-1, cnt + 1, not is_day))  # 벽을 부수고 이동

                # 밤일 때 벽을 부술 수 없으므로 현재 위치에서 대기
                else:
                    if map[R][C] == 1 and k > 0 and visit[R][C][k-1] == 0:
                        visit[r][c][k] += 1  # 현재 위치에서 머무름
                        q.append((r, c, k, cnt + 1, not is_day))  # 낮/밤 변경 후 다시 큐에 추가

    # 도착하지 못한 경우 -1 출력
    if not success_flg:
        print(-1)

# BFS 탐색 실행
search(field, visited)

GPT가 깔끔하게 주석 달아준 코드이다.