백준 14442 [벽 부수고 이동하기 2] 파이썬

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

 

다행히 이전에 풀었던 문제의 풀이법이 떠올라 쉽게 풀었다.

https://dongkam.tistory.com/435

백준 1600 [말이 되고픈 원숭이] 파이썬

 

위 문제와 마찬가지로 3차원 배열을 생성하여, 벽을 부수는 경우와 그렇지 않은 경우에 대하여 경우를 나누어 탐색한다.

 

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())))  # 문자열을 정수 리스트로 변환하여 저장

# 방문 여부 저장 리스트 (N x M 크기, K+1 개의 벽 부수기 상태를 저장)
visited = [[[0 for _ in range(K+1)] for _ in range(M)] for _ in range(N)]

def search(map, visit):
    success_flg = False  # 목적지 도착 여부 확인 변수
    q = deque()  # BFS 탐색을 위한 큐
    q.append((0, 0, K))  # 시작 위치 (0,0)에서 K개의 벽을 부술 수 있는 상태
    visited[0][0][K] = 1  # 시작 위치 방문 처리 (이동 횟수를 1로 설정)

    while q:
        r, c, k = q.popleft()  # 현재 위치 (r, c)와 남은 벽 부수기 횟수 (k) 가져오기

        # 목표 지점 (N-1, M-1)에 도착하면 결과 출력 후 종료
        if r == N - 1 and c == M - 1:
            success_flg = True
            print(visit[r][c][k])  # 현재까지의 이동 거리 출력
            break

        # 네 방향으로 이동
        for i in range(4):
            R = r + dr[i]
            C = c + dc[i]

            # 맵 범위 내에 있을 경우
            if 0 <= R < N and 0 <= C < M:
                # 벽이 아닌 경우 (0)이고 방문하지 않은 곳이면 이동
                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))  # 다음 탐색을 위해 큐에 추가
                
                # 벽 (1)이고, 벽을 부술 수 있는 경우 (k > 0)
                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))  # 벽을 부수고 이동한 상태를 큐에 추가

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

# 탐색 실행
search(field, visited)

GPT가 깔끔하게 주석을 달아준 코드이다. (주석만 달아줬습니다.)