개미의 개열시미 프로그래밍

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

알고리즘/DFS, BFS, 백트래킹

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

YunHyeok 2021. 6. 8. 19:40
728x90
반응형

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

 

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

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

 

 

풀이코드

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 단계별 풀기를 문제없이 풀었다면 쉬운문제라고 생각합니다.

 

728x90
반응형
Comments