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

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

7562번: 나이트의 이동

이번 문제는 이동방향이 상하좌우가 아닌 대각선방향으로 되어있다. 즉 기존의 4개의 방향에서 8개의 방향으로 늘어난거다. 그렇기 때문에 이동방향또한 8개로 선언해서 풀어준다.

그외의 요소들은 기존 bfs 문제들과 동일하게 풀었다.

설명은 아래 코드의 주석을 달아놓았다.

 

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())

dx = [1,2,-1,-2,1,2,-1,-2] # 문제에 주어진 8개의 방향을 선언해준다.
dy = [2,1,2,1,-2,-1,-2,-1]

def bfs(a,b,x,y): #출발지점(a,b) 도착지점(x,y)를 파라미터로 잡아준다
    q=deque()
    q.append((a,b))
    visited[a][b] = 1 # 첫 스타트 지점을 1로 시작
    
    while q:
        x1,y1 = q.popleft()
        
        if x == x1 and y == y1: # popleft()의 좌표가 최종 목적지와 같을때 
            print(visited[x][y]-1) # -1을 하는 이유는 29번줄에서 더했기 때문에 빼줘야한다.
            break
        
        for i in range(8):
            nx = x1+dx[i]
            ny = y1+dy[i]
            
            if 0<=nx<I and 0<=ny<I and visited[nx][ny] == 0:
                q.append((nx,ny))
                visited[nx][ny] =visited[x1][y1]+1 # 좌표가 변경될때마다 +1씩 더해주며 최종목적지에 
                                                   # 도달했을때의 값을 출력해주면 최소 이동거리가 나온다.
    

for _ in range(T):
    I = int(input())
    a,b = map(int,input().split())
    x,y = map(int,input().split())
    
    visited = [[0]*I for _ in range(I)]
    bfs(a,b,x,y)

특별히 코멘트가 필요한 문제는 아닌거 같다.

전형적인 최단거리를 찾는 bfs 문제이다.