백준 2206 벽 부수고 이동하기 파이썬 풀이

난이도 : 골드3

풀이일 : 05125

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

2206번: 벽 부수고 이동하기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
arr = [sys.stdin.readline().strip() for _ in range(N)]
visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
shift = []    # 도착지까지의 이동 횟수

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]    # 이동 가능 좌표

queue = deque()
queue.append((0, 0, 0))
visited[0][0][0] = 1
while queue:
    x, y, z = queue.popleft()
    if x == N-1 and y == M-1:    # 도착 시 이동 수 저장
        shift.append(visited[x][y][z])
    for k in range(4):
        nx, ny, nz = x + dx[k], y + dy[k], z
        # 벽 부수기 불가능 시
        if z and 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == '0' and not visited[nx][ny][nz]:
            queue.append((nx, ny, nz))
            visited[nx][ny][nz] = visited[x][y][z] + 1
        # 벽 부수기 가능 시
        if not z and 0 <= nx < N and 0 <= ny < M and not visited[nx][ny][z]:
            if arr[nx][ny] == '1':    # 벽을 부순 경우
                nz = z + 1
            queue.append((nx, ny, nz))
            visited[nx][ny][nz] = visited[x][y][z] + 1

print(min(shift) if shift else -1)

코드 구성

• 공백이 없으니 분리해서 입력 받기
• 벽을 부쉈는지 확인 위한 삼차원 배열 생성
• 위치 정보와 함께 벽 부쉈는지 정보 함께 전달
• 도착 가능 시, 이동 수 리스트에 저장
• 벽 부순 적이 있는지에 따라 arr[nx][ny] 조건 추가

---

느낀점

삼차원 배열을 사용하는 문제도 엄청 재밌다.

비슷한 문제들을 모아서 풀면서 조금씩 달라지는 조건들을 고려하는 풀이가 재밌어서 내일 기차에서도 시도해봐야지

기차에서 집중해서 문제 여러개 풀어둬야겠다 프로젝트 기간동안 못풀테니까