S1 7562. 나이트의 이동

문제 보기 :  7562번: 나이트의 이동

---

문제

• 정답률 : 52%

---

작성 코드

from collections import deque

# 체스판 위 기사(Knight)의 이동 방향
directions = [(-2,-1),(-1,-2),(-2,1),(-1,2),(2,-1),(1,-2),(2,1),(1,2)]

## 기사의 이동
def knight(graph,start):
    graph[start[0]][start[1]]=0
    visited[start[0]][start[1]]=True
    dd = deque([start])
    while dd:
        x,y = dd.popleft()
        for dx,dy in directions:
            xx= x+dx; yy = y+dy
            if 0<=xx<n and 0<=yy<n and graph[xx][yy]==-1 and not visited[xx][yy]:
                graph[xx][yy] = graph[x][y]+1 #이동횟수 업데이트
                visited[xx][yy] = True #방문 여부 표시 변경
                dd.append((xx,yy))

T = int(input())
for _ in range(T):
    n = int(input())

    # 정사각형의 체스판 (방문 횟수)
    graph = [[-1]*n for _ in range(n)]
    # 방문 여부 표시 체스판
    visited = [[False]*n for _ in range(n)]

    # 시작점, 목표점
    startx,starty = map(int,input().split())
    endx,endy = map(int,input().split())

    # 기사의 이동 실행
    knight(graph,(startx,starty))

    # 목표점까지의 이동 횟수 출력
    print(graph[endx][endy])

---

풀이

체스판 위에 있는 기사는 현재 위치에서 directions에 있는 방향으로 이동한다.

이를 활용해 기사의 이동 함수를 구현했다. 함수는 dd에 남은 좌표가 없을 때까지 이동횟수와 방문여부 표시를 변경하는 방식으로 구현되며, graph 내 초기값을 -1로 둠으로써 방문 여부도 동시에 확인할 수 있다.

그래서 음.. visited는 생략해도 될 것 같지만 일단은 추가해두었다.