[BOJ] 7562. 나이트의 이동

Jimeaning·2023년 6월 22일

BFS 그래프

코딩테스트

목록 보기

102/143

Python3

문제

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

키워드

그래프 탐색
너비 우선 탐색

문제 풀이

문제 요구사항

나이트가 최소 몇 번만에 이동할 수 있는지 출력하는 프로그램

변수 및 함수 설명

t: 테스트 케이스의 개수
l: 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)
x, y: 나이트가 현재 있는 칸
desx, desy: 나이트가 이동하려고 하는 칸

queue: bfs 연산 시 사용되는 큐
visited: 나이트가 방문한 곳
curX, curY: 현재 있는 칸
nx, ny: 다음에 이동할 칸

풀이

(입력 및 선언)

테스트 케이스 개수를 입력받는다
테스트 케이스 수만큼 반복

체스판의 크기 입력받기 (l × l)
나이트의 현재 위치와 목적지 위치 입력받기
큐와 visited 리스트 선언
큐에 현재 위치를 넣고, 방문처리
bfs 함수 호출

(bfs 함수)

큐에 원소가 있을 때까지 반복
현재 위치가 목적지 위치와 같아진다면 visited 리스트를 반환하고 반복문 종료
참고) 처음 위치에 1로 방문처리 해주었기 때문에 1을 빼준다
나이트가 이동할 수 있는 경우의 수는 총 8가지이기 때문에 8번 반복한다
다음 이동하고자 하는 칸이 맵 안(0, ..., l-1)에 있고, 방문하지 않은 곳이라면
방문처리를 하고 큐에 다음 이동할 위치를 넣는다.

최종 코드

from collections import deque

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

t = int(input())

def bfs():
    while queue:
        curX, curY = queue.popleft()
        if curX == desx and curY == desy:
            return visited[desx][desy] - 1
        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            if 0 <= ny < l and 0 <= nx < l and visited[nx][ny] == 0:
                visited[nx][ny] = visited[curX][curY] + 1
                queue.append((nx, ny))

for _ in range(t):
    l = int(input())
    x, y = map(int, input().split())
    desx, desy = map(int, input().split())
    
    queue = deque()
    visited = [[0 for _ in range(l)] for _ in range(l)]
    
    queue.append((x, y))
    visited[x][y] = 1
    print(bfs())