[Python] 나이트의 이동 (백준 7562번 파이썬)

 

나이트의 이동

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

52823

27465

20436

50.908%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

 

 

문제 이해

- 체스판에서 시작점을 기준으로 나이트를 움직여 목표점까지의 최단 거리를 찾는 문제입니다.

- 최단거리 문제이므로 BFS탐색을 사용해서 해결할 수 있습니다.

 

문제 풀이 아이디어

문제 풀이

- 일반적으로 사용하는 BFS 방법에서 방향벡터를 정의하는 방식과, 방문처리를 하는 방법에 변화를 주었습니다.

- 방문처리를 할 때 0과 1로 표현하는 것이 아니라, 방문하지 않은 칸은 0, 이외에는 현재 노드 레벨(그림 참고)에 +1 한 값을 채웁니다.(시작점이 1이며, +1씩 더해 최단거리를 찾기 위함)

- 노드레벨이 증가할 때마다 1씩 증가하며, 현재 탐색하는 x,y값이 목표지점과 같으면 종료합니다.

- 앞에서 최초 노드(예1의 경우 0,0)의 값을 1로 설정했기 때문에, 결과값에서 1을 빼줍니다.

 

코드

#7562 나이트의 이동
from collections import deque

t = int(input())
for _ in range(t):
    n = int(input())
    visited = [[0]*n for _ in range(n)]
    x,y = map(int, input().split())
    a,b = map(int, input().split())
    q = deque()

    dx = [-1,-2,-2,-1,1,2,2,1]
    dy = [-2,-1,1,2,2,1,-1,-2]

    q.append((x,y))
    visited[x][y]=1
    
    while q: #BFS실행
        x,y = q.popleft()
        if x==a and y==b: #목표 칸에 다다르면 종료
            result = visited[x][y]
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and ny>= 0 and nx < n and ny < n and visited[nx][ny]==0:
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y]+1
    print(result-1) #BFS실행 전에 visited[x][y]=1이기 때문.