[백준] 7562 나이트의 이동 (파이썬/python)

🎈문제

https://www.acmicpc.net/problem/7562

 

🎁어떤 알고리즘?

1. 움직여야하는 '최소 횟수'를 알아야 하므로 당연히 BFS를 사용해야한다.

2. 상하좌우 움직임을 고려해주면 되는 일반적인 BFS와는 다르게 나이트의 움직임을 고려해줘야 한다.

3. 나머지는 다른 쉬운 bfs문제들과 다를바가 없다.

 

💻코드

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

# 2. bfs
def bfs(x,y):
    board[x][y] = 0 # 초기 나이트의 위치 0으로 초기화
    deq = deque()
    deq.append([x,y])
    dx = [-2,-1,1,2,2,1,-1,-2]  # 나이트의 움직임 좌표
    dy = [1,2,2,1,-1,-2,-2,-1]
    while deq:
        x,y = deq.popleft()
        if board[tar_i][tar_j] != -1:   # 탈출 조건
                print(board[tar_i][tar_j])
                return
        for i in range(8):  # 8방향으로 각각 돌아보기위한 for문
            nx = x + dx[i]
            ny = y + dy[i]
            # board 밖으로 나가면 밑의 코드 실행 x
            if nx < 0 or nx > (l-1) or ny < 0 or ny > (l-1):
                continue
            if board[nx][ny] == -1: # 나이트가 한번도 오지 않은 좌표면
                board[nx][ny] = board[x][y] + 1 # 좌표에 나이트의 움직인 횟수 +1
                deq.append([nx,ny])
    return


# 1. input
t = int(input())    # test case
for _ in range(t):
    l = int(input())    # 체스판 한 변의 크기
    board = [[-1 for j in range(l)] for i in range(l)]
    now_i,now_j = map(int,input().split())  # 나이트 초기 위치
    tar_i,tar_j = map(int,input().split())  # 나이트 목표 위치
    bfs(now_i,now_j)    # 탐색

🎄코드 설명

1. bfs(now_i, now_j)와 같이 나이트의 초기 위치만을 파라미터로 받는 이유는 나이트의 현재 위치가 계속해서 업데이트 되기 때문이다. 나이트의 목표 위치는 바뀌는 값이 아니므로 파라미터값으로 나이트의 초기 위치만을 받도록 했다.

 

2. bfs 문제를 몇 번 풀어봤다면 나이트의 움직임을 고려하여 dx, dy 변수에 적절한 값을 넣어 줄 수 있게 된다. 이 부분이 헷갈린다면 https://chjcoder.tistory.com/2 이 문제와 같이 상하좌우 움직임만을 고려하는 bfs 문제를 풀어보자. 

 

3. 좌표는 다음과 같다.