[파이썬] 백준 30894 : 유령의 집 탈출하기 (골드1)

[파이썬] 백준 30894 : 유령의 집 탈출하기 (골드1)

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

---

풀이

방향성 생각

• 맵 정보를 입력받고, 시간에 따른 이동 가능/불가능 배열을 만든다.
  • 이동할 때 마다 유령기준으로 체크를 하면 cost가 커보인다.
  • ban[mod][y][x]로 mod = t%4로 설정해서 각 시간대에 해당 위치가 접근 가능한지 저장한다.
• 나머지는 BFS랑 비슷하게 풀 수 있다.
• 제자리 구현이 있어서 TLE만 없다면 다익으로도 풀 수 있다.
  • 아마 TLE도 안날듯?
  • 제자리를 구현할 때, 해당 방향으로 이동 시 기다려야하면 기다리는 시간을 같이 더해주면 된다.
  • 사실 BFS로 이런 방식으로 풀 수 있는데, cur_time이라는 변수를 하나 두고 시간이 cut_time과 0 또는 1차이가 나는 경우에만 탐색을 진행하게 만들어주고, 차이가 2 이상인 경우 큐의 맨 뒤로 넘기면 된다.

 

---

파이썬

from collections import deque
import sys

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y: 0<=x<W and 0<=y<H
INF = float('inf')
dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W = map(int,input().split())
sy,sx,ey,ex = map(lambda x : int(x)-1, input().split())

arr = [list(input()) for _ in range(H)]

# ban 배열 업데이트 하기
ban = [[[False]*W for _ in range(H)] for _ in range(4)]
for y in range(H):
    for x in range(W):

        # 유령이 있는 위치는 이동 불가
        if arr[y][x] == '#':
            for i in range(4):
                ban[i][y][x] = True

        # 시간대 t%4, 해당 시점에서 유령이 쳐다보는 방향 (dire+4)%4
        elif arr[y][x] != '.':
            dire = int(arr[y][x])
            for t in range(4):
                ban[t%4][y][x] = True
                dx,dy = dires[(dire+t)%4]
                nx,ny = x+dx,y+dy
                while inside(nx,ny):
                    if arr[ny][nx] == '.':
                        ban[t%4][ny][nx] = True
                        nx += dx
                        ny += dy
                    else:
                        break

def bfs():

    V = [[[-1]*W for _ in range(H)] for _ in range(4)]
    V[0][sy][sx] = 0
    Q = deque([(sx,sy,0)])

    while Q:
        x,y,t = Q.popleft()
        nt = t+1

        if (x,y) == (ex,ey):
            return t

        # 제자리 이동
        if not ban[nt%4][y][x] and V[nt%4][y][x] == -1:
            Q.append((x,y,nt))
            V[nt%4][y][x] = nt

        # 이동하기
        for dx,dy in dires:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and not ban[nt%4][ny][nx] and V[nt%4][ny][nx] == -1:
                Q.append((nx,ny,nt))
                V[nt%4][ny][nx] = nt

    return 'GG'

print(bfs())

---

코멘트

• 잔실수 줄이기... 주석 달면서 하기