[파이썬] 백준 16959 : 체스판 여행 1 (플레5)

[파이썬] 백준 16959 : 체스판 여행 1 (플레5)

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

 

---

풀이

방향성 생각

• 다차원 BFS
• N=10인데 위치만으로 visit 배열을 만들게 되면 방문 처리가 제대로 되지 않는다.
• 위치 + 현재 사용하는 말 + 방문한 숫자(현재 위치가 아니라, 1~N^2까지 방문 중 몇번째인지)

---

전체코드

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:[(x,y) for x in (1,-1) for y in (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 i in range(3):
    V[i][1][sy][sx] = 0

Q = deque([tuple((sx,sy,0,i,1)) for i in range(3)]) # x,y,t,말,현재숫자
while Q:

    x,y,t,c,v = Q.popleft()

    # 말 바꾸기 : 다른 말로 v까지 찾은 상태에서 해당 좌표 x,y에 접근 안했을 때 다른 말로 변경
    for nc in range(3):
        if V[nc][v][y][x] == -1 and c!=nc:
            Q.append((x,y,t+1,nc,v))
            V[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
            # 해당 방향으로 이동 못하게 되면 룩, 비숍 탈출 or 나이트는 1 step만 가능
            if not inside(nx,ny) or v==N**2 or (c==0 and step>1):
                break

            # v까지 찾은 상태에서 다음 숫자 v+1을 방문
            if V[c][v+1][ny][nx] == -1 and arr[ny][nx] == v+1:
                Q.append((nx,ny,t+1,c,v+1))
                V[c][v+1][ny][nx] = t+1

            # v까지 찾은 상태에서 다음 숫자를 못찾은 경우
            elif V[c][v][ny][nx] == -1 and arr[ny][nx] != v+1:
                Q.append((nx,ny,t+1,c,v))
                V[c][v][ny][nx] = t+1

print(min(V[i][-1][ey][ex] for i in range(3)))

---

코멘트

• 이왜플?