7562

날짜 : 2023. 02. 14

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

t = int(sys.stdin.readline()) # 테스트케이스


def bfs(r1, c1, r2, c2, r): # 시작, 도착, 변의 길이
    q = deque()
    cnt = 0 # 이동횟수
    q.append([r1, c1, cnt])
    dx = [-2, -1, 1, 2, 2, 1, -1, -2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]
    while q:
        x, y, c = q.popleft()
        for i in range(8):
            x1 = x + dx[i]
            y1 = y + dy[i]
            if x1 in range(r) and y1 in range(r): # 범위에 포함
                if x1 == r2 and y1 == c2:  # 방문
                    print(c+1) # 이동횟수 출력
                    return
                if not graph[x1][y1]:
                    graph[x1][y1] = True # 방문처리
                    q.append([x1, y1, c+1]) # 큐에 삽입


for _ in range(t):
    l = int(sys.stdin.readline()) # 한 변의 길이
    graph = [[False] * l for _ in range(l)]
    r1, c1 = map(int, sys.stdin.readline().split()) # 시작
    r2, c2 = map(int, sys.stdin.readline().split()) # 도착
    if r1 == r2 and c1 == c2 :
        print(0)
        continue
    bfs(r1, c1, r2, c2, l)

 

 

풀이

- 최소 탐색길이를 찾는 것이기 때문에 BFS를 활용해서 풀이하는 문제였다.

- 테스트케이스마다 기본 그래프를 초기화 한 후 풀도록 주의해야했다.

 

 

 

알게된 점

- 

 

 

참고 사이트

-