[파이썬] 백준 16952 : 체스판 여행 2 (플레4)

[파이썬] 백준 16952 : 체스판 여행 2 (플레4)

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

 

---

풀이

방향성 생각

• BFS or 다익(조건 2개라서)
• 배열을 하나 더 만들어서 $O(N^43400)$이라 다익으로 풀면 터질거같아서 BFS로 풀이
  • 다른 방법은 생각이 잘...
• 숫자 a에서 b까지 이동하는데 룩,비숍으로 변경하면 최대 4번 걸린다 (현재 위치에서 변경 -> 이동 -> 이동위치에서 변경 -> 이동 : 총 4초)
• 1부터 100까지 찾는거니까 최대 변경 횟수 400으로 생각
• 더미큐를 제거하기 위해서 정답을 처음 찾은 시간 t를 찾으면 flag를 세우고, t+1 정보를 popleft 시키면 while문을 탈출한다.

 

---

전체코드

from collections import deque
inside = lambda x,y : 0<=x<N and 0<=y<N

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

# 시작 / 끝 위치
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            sx,sy = j,i
        if arr[i][j] == N**2:
            ex,ey = j,i

# 나이트 비숍 룩
dire = {0:[(x,y) for x in (1,2,-1,-2) for y in (1,2,-1,-2) if abs(x)+abs(y)==3],
         1:[(1,1),(1,-1),(-1,1),(-1,-1)],
         2:[(1,0),(-1,0),(0,-1),(0,1)]}

# V[변경횟수][밀][현재 숫자][y][x]
V = [[[[[-1]*N for _ in range(N)] for _ in range(N**2+1)] for _ in range(3)] for _ in range(401)]
for i in range(3):
    V[0][i][1][sy][sx] = 0


find = False
Q = deque([tuple((sx,sy,0,i,1,0)) for i in range(3)])
while Q:

    x,y,t,c,v,change = Q.popleft()
    
    # 정답을 찾은 경우 걸린 시간 t
    if not find and (x,y,v) == (ex,ey,N**2):
        find = t
        continue
    
    # 정답 찾았고 t보다 크면 더이상 탐색할 필요 x
    if find and find < t:
        break
    
    # 말 바꾸기
    for nc in range(3):
        if c!=nc and change+1 < 401 and V[change+1][nc][v][y][x] == -1:
            Q.append((x,y,t+1,nc,v,change+1))
            V[change+1][nc][v][y][x] = t+1

    # 말 이동하기
    for dx,dy in dire[c]:
        for step in range(1,N):
            nx,ny = x+dx*step,y+dy*step

            if not inside(nx,ny) or (c==0 and step>1):
                break

            nv = v + (arr[ny][nx] == v+1)
            if V[change][c][nv][ny][nx] == -1:
                Q.append((nx,ny,t+1,c,nv,change))
                V[change][c][nv][ny][nx] = t+1

answer = []
for change in range(401):
    for c in range(3):
        if V[change][c][-1][ey][ex] != -1:
            answer.append((V[change][c][-1][ey][ex],change))
answer.sort()
print(*answer[0])

---

코멘트

• 5차원이라 dict이 조금 더 빠를거같았는데 TLE...