[알고리즘/BFS & DFS] 7562번 : 나이트의 이동 - python

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

7562번: 나이트의 이동

 

---

• 문제
• 소요시간: 42분 2초

---

• 설계하기(접근방법) 

1. 입력받기

문제의 요구사항을 입력받는다

 

2. 구현하기

이 문제의 핵심은 평상시 풀던 문제와는 좌표설정이 다르다는 점이다

dx = [0, 0, 1, -1]

dy = [1, -1, 0 ,0]

이었던 1칸씩 탐지하던 것을

나이트의 이동방식대로 바꾸면 쉽게 풀 수 있다

 

3. 출력하기

목표 좌표로 가는 최단거리를 구한다

 

 

---

• 코드(출력)

from collections import deque

def bfs(x, y) :
    dx = [-2, -1, 1, 2, -2, -1, 1, 2]
    dy = [-1, -2 ,-2 ,-1 ,1 ,2 ,2 ,1]
    q = deque()
    q.append([x,y])
    while q:
        x,y = q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < length and 0 <= ny < length:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx, ny])



for _ in range(int(input())):
    length = int(input())
    x ,y = map(int, input().split())
    visited = [[0] * (length) for _ in range(length) ]
    target_x, target_y = map(int, input().split())
    visited[x][y] = 0
    bfs(x, y)
    if target_x == x and target_y == y:
        print(0)
    else:
        print(visited[target_x][target_y])

---

• 얻어갈 부분

1. 범위를 잘못 조절하여 디버깅 시간이 오래 걸렸다. 범위 연산자를 통일하는 습관을 기르자

2. q.append()를 하지 않아서 초반에 실수가 났다. bfs 유형에 유의하자