[파이썬] 백준 18224 : 미로에 갇힌 건우 (골드1)

[파이썬] 백준 18224 : 미로에 갇힌 건우 (골드1)

• https://www.acmicpc.net/problem/18224

---

풀이

방향성 생각

• 다른 BFS 문제와 다르게 기다리는 로직을 구현하는 것이 아니라, 움직여야만 시간이 흘러가는 문제이다.
• 밤이라고 해서, 모두 같은 밤은 아니다.
  • 밤이어도 움직인 횟수에 따라서 벽을 건넌 후에 움직임이 달라질 수 있다.
  • 배열을 2*M (cycle)만큼 차원을 늘려서 만든다
• 나머지는 비슷하게 BFS로 구현
  • 현재가 밤인 경우 다른 미끄러지는 문제처럼 nnx,nny를 두고 while문에서 조건 처리

 

---

전체코드

from collections import deque
import sys

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<N and 0<=y<N

dires = [(1,0),(0,1),(-1,0),(0,-1)]

N,M = map(int,input().split())
cycle = 2*M 

arr = [list(map(int,input().split())) for _ in range(N)]

V = [[[-1]*N for _ in range(N)] for _ in range(cycle)] # V[이동횟수%cycle][y][x]
V[0][0][0] = 0

Q = deque([(0,0,0)])
while Q:
    x,y,t = Q.popleft()

    for dx,dy in dires:
        nx,ny = x+dx,y+dy

        if inside(nx,ny) and V[(t+1)%(2*M)][ny][nx] == -1:

            # 그냥 이동 가능한 경우
            if arr[ny][nx] == 0:
                Q.append((nx,ny,t+1))            
                V[(t+1)%(2*M)][ny][nx] = t+1
            # 벽인 경우
            else:
                # 밤인 경우에 이동 가능
                if not (0<= t%cycle < M):

                    # 유효성 검사
                    can_move = True
                    nnx,nny = nx,ny
                    while True:
                        nnx += dx
                        nny += dy
                        if not inside(nnx,nny):
                            can_move = False
                            break
                        if arr[nny][nnx] == 0:
                            break
                    # 움직일 수 있고, 첫 방문
                    if can_move and V[(t+1)%cycle][nny][nnx] == -1:
                        V[(t+1)%cycle][nny][nnx] = t+1
                        Q.append((nnx,nny,t+1))

if all(V[i][-1][-1] == -1 for i in range(cycle)):
    print(-1)
else:
    answer = min(V[i][-1][-1] for i in range(cycle) if V[i][-1][-1] != -1)
    day = (answer // (2*M)) + 1 
    print(day, 'sun' if (answer%cycle)<M else 'moon')

코멘트

• .