[BOJ 20158, Python 3] 사장님 달려가고 있습니다

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

20158번: 사장님 달려가고 있습니다

 

 

풀이

지문을 읽어보면 BFS 알고리즘인 것을 알 수 있지만, 지문 내용이 구현하기가 참 까다롭습니다.

 

주의 할 점

• 가속도
  • 같은 방향으로 달릴 경우 가속도가 붙는데, 속도 조절이 불가능함
  • 방향 전환을 해야 1초에 1칸씩 달릴 수 있게 됨
• 통제 구역
  • 가속도가 붙은 채로 통제 구역을 이동하면 [도중에 지나가는 통제 구역의 통제 시간] > [움직이기 시작할 때의 시간]이면 넘어갈 수 있음
  • 도착한 구역이 통제 구역이고, 도착한 시간과 통제 구역의 통제 시간이 같으면 그 곳은 갈 수 없음

 

이 주의점을 보면 S의 방향에 따라 다른 visit 배열을 잡고, BFS를 돌려야 합니다.(= visited[N][N][4])

가속도가 붙어 움직일 때, flag = True 값을 하나 만들어서 맵 밖에까지 나가거나 도중에 이미 닫힌 통제 구역이 있으면 flag = False로 해주어 큐에 움직인 좌표를 넣어주지 말아야 합니다.

그리고 BFS를 돌리다가 도착한 시간과 통제 구역의 통제 시간이 같을 경우엔 큐에 해당 좌표를 넣지 않아야 합니다.

 

 

코드

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
input = __import__('sys').stdin.readline
 
n = int(input())
MAP = [[*map(int, input().split())] for _ in range(n)]
S = [[[[-1] * 15 for ___ in range(4)] for __ in range(n)] for _ in range(n)]
inq = [[[[0] * 15 for ___ in range(4)] for __ in range(n)] for _ in range(n)]
q = deque([[0, 0, 0, 0], [0, 0, 2, 0]]) # x, y, 방향, 가속도
for i in range(4):
    S[0][0][i][0] = 0
while q:
    x, y, d, a = q.popleft()
    inq[x][y][d][a] = 0
    if x == y == n - 1:
        print(S[x][y][d][a])
        exit()
    a += 1
    flag = True
    for i in range(a):
        nx, ny = x + dx[d] * (i + 1), y + dy[d] * (i + 1)
        if nx < 0 or nx >= n or ny < 0 or ny >= n or not (MAP[nx][ny] == 0 or MAP[nx][ny] >= S[x][y][d][a-1]):
            flag = False
            break
    if flag:
        nx, ny = x + dx[d] * a, y + dy[d] * a
        if (MAP[nx][ny] == 0 or S[x][y][d][a-1] + 1 < MAP[nx][ny]) and S[nx][ny][d][a] == -1 and inq[nx][ny][d][a] == 0:
            q.append([nx, ny, d, a])
            S[nx][ny][d][a] = S[x][y][d][a-1] + 1
            inq[nx][ny][d][a] = 1
    for i in range(4):
        if d == i: continue
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and (MAP[nx][ny] == 0 or S[x][y][d][a-1] + 1 < MAP[nx][ny]) and S[nx][ny][i][1] == -1 and inq[nx][ny][d][a] == 0:
            S[nx][ny][i][1] = S[x][y][d][a-1] + 1
            q.append([nx, ny, i, 1])
            inq[nx][ny][i][1] = 1
print('Fired')