[알고리즘] 백준7562 나이트의 이동 - 파이썬

단계별 풀기 dfs, bfs의 8문제입니다.. 한문제만 더 풀면 다른 파트를 공부할 수 있습니다ㅜ

 

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

7562번: 나이트의 이동

 

 

풀이코드

from collections import deque
from sys import stdin


def bfs(x, y):
    # 나이트의 이동범위
    dx = [-1, 1, -2, 2, -2, 2, -1, 1]
    dy = [-2, -2, -1, -1, 1, 1, 2, 2]
    queue = deque()
    queue.append([x, y])

    while queue:
        x, y = queue.popleft()
        if x == n and y == m:
            print(graph[x][y])
            break

        for i in range(8): # 나이트의 이동
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < l and 0 <= yy < l and graph[xx][yy] == 0:
                graph[xx][yy] = graph[x][y] + 1
                queue.append([xx, yy])


n = int(input())
for _ in range(n):
    l = int(input())
    graph = [[0]*l for _ in range(l)] # 체스판 생성
    x, y = map(int, stdin.readline().split()) # 현재 있는 칸
    n, m = map(int, stdin.readline().split()) # 목표지점의 칸
    bfs(x, y)

 

문제풀이

: 이번 문제는 난이도가 좀 쉬운편이라고 생각된 문제입니다. 기존 목표지점까지의 최단거리를 풀때의 bfs를 풀이를 참고하면 되고 단, 상하좌우가 아닌 나이트의 이동범위를 생각해서 dx, dy 배열을 위의 코드처럼 작성하였습니다. 지금까지 dfs, bfs 단계별 풀기를 문제없이 풀었다면 쉬운문제라고 생각합니다.