[백준] 7562번: 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562

문제

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

입력

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

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

출력

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

---

우선 입력을 구현하자.

세 줄에 걸쳐 체스판 한 변의 길이,  현재 나이트의 좌표, 나이트의 목적지가 주어진다.

 

testCase = int(input())

for _ in range(testCase):
    l = int(input())
    curCoor = tuple(map(int, input().split()))
    dstCoor = tuple(map(int, input().split()))

 

너비 우선 탐색 (BFS)를 이용해서 구현할 수 있어보인다.

체스판을 좌표로 하고 나이트가 이동할 수 있는 칸을 리스트로 저장해준다.

knightMv = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]

 

그 다음 현재 좌표에서 knigthMv 리스트의 원소를 하나씩 반복해 더해주면서 이동할 수 있는 칸을 찾는다.

이후 도착한 좌표에 현재 좌표까지 도달하는데 걸리는 이동 횟수를 더해준다.

마지막으로 목표 지점에 도달하면 loop를 break하고 해당 좌표까지 걸린 도달 횟수를 출력해주면 된다.

 

from collections import deque

def BFS(l, start:tuple, end:tuple):
    
    knightMv = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]

    visited = [[0 for i in range(l)] for j in range(l)] # 체스판 모든 칸을 0으로 초기화
    q = deque()
    q.appendleft(start)

    while q:

        curCoor = q.pop()
        for mv in knightMv:	# 현재 좌표에서 나이트가 움직일 수 있는 위치를 각각 더해준다
            
            if (curCoor[0]+mv[0]<0 or curCoor[0]+mv[0]>=l): # x 좌표 범위 확인
                continue
            if (curCoor[1]+mv[1]<0 or curCoor[1]+mv[1]>=l): # y 좌표 범위 확인
                continue
            if visited[curCoor[0]+mv[0]][curCoor[1]+mv[1]]: # 방문 여부 확인
                continue
            
            q.appendleft((curCoor[0]+mv[0],curCoor[1]+mv[1]))
            visited[curCoor[0]+mv[0]][curCoor[1]+mv[1]] = visited[curCoor[0]][curCoor[1]] + 1

        if visited[end[0]][end[1]]:
            break

    return visited[end[0]][end[1]]

 

이 상태에서 테스트 케이스를 돌려봤더니 시작 지점과 도착  지점이 같은 경우 이동 횟수가 2로 출력된다.

마지막 예외처리를 해주었다. 

    if start == end:
        return 0

 

최종 코드는 아래와 같다. 

from collections import deque

def BFS(l, start:tuple, end:tuple):

    if start == end:
        return 0
            
    knightMv = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]

    visited = [[0 for i in range(l)] for j in range(l)]
    q = deque()
    q.appendleft(start)

    while q:

        curCoor = q.pop()
        for mv in knightMv:
            
            if (curCoor[0]+mv[0]<0 or curCoor[0]+mv[0]>=l): 
                continue
            if (curCoor[1]+mv[1]<0 or curCoor[1]+mv[1]>=l):
                continue
            if visited[curCoor[0]+mv[0]][curCoor[1]+mv[1]]:
                continue
            
            q.appendleft((curCoor[0]+mv[0],curCoor[1]+mv[1]))
            visited[curCoor[0]+mv[0]][curCoor[1]+mv[1]] = visited[curCoor[0]][curCoor[1]] + 1

        if visited[end[0]][end[1]]:
            break

    return visited[end[0]][end[1]]


testCase = int(input())

for _ in range(testCase):

    l = int(input())
    strCoor = tuple(map(int, input().split()))
    dstCoor = tuple(map(int, input().split()))
    
    print(BFS(l, strCoor, dstCoor))

 

역시 파이썬이 좋다.