[백준] 7562 나이트의 이동

백준 7562번 나이트의 이동

그래프 / 너비우선탐색

 

 

[문제]

 

bfs를 돌리고 이동할때마다 +1을 해주면 되는 문제

 

 

 

[과정]

 

핵심이 되는 부분은 나이트가 이동할 수 있는 좌표를 nx,ny로 두는 것

기존은 보통 상하좌우로 이동했었던 부분을 해당 그림의 이동거리에 맞게 좌표를 넣어주고 bfs를 수행하면 됨

 

 

• 입력받는 부분에서 arr배열을 0으로 체스판길이 만큼 초기화      <- 해당부분에서 0인지 비교를 통해 visited를 동시에 수행
• 만약 시작점과 도착점이 같다면 0을 출력
• 나머지의 경우에 bfs수행
  • 첫 조건문으로 도착점의 위치에 도달했다면 해당 위치의 값을 리턴
  • 체스판의 이동 경우의 수만큼 이동
    • 거리를 벗어나면 예외처리
    • arr의 다음 이동할 좌표의 값이 0이라면(방문하지 않았다면) 큐에 해당 좌표를 넣고 이동거리 +1

 

 

 

 

[소스코드]

 

# 나이트의 이동

from collections import deque
import sys
input = sys.stdin.readline

dx = [-2,-1,-2,-1,1,2,1,2]   # 왼쪽위, 왼쪽아래, 오른쪽위, 오른쪽아래
dy = [-1,-2,1,2,-2,-1,2,1]

def bfs(arr, x1, y1, x2, y2, l):
    q = deque()
    q.append((x1,y1))
    arr[x1][y1] = 1

    while q:
        x,y = q.popleft()
        if x == x2 and y == y2:
            return arr[x2][y2]-1
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= l or ny >= l:
                continue
            if arr[nx][ny] == 0:
                q.append((nx,ny))
                arr[nx][ny] = arr[x][y] + 1
    

for _ in range(int(input())):
    l = int(input())
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())

    arr = [[0]*l for _ in range(l)]
    if x1 == x2 and y1 == y2:
        print(0)
        continue
    result = bfs(arr, x1, y1, x2, y2, l)
    print(result)

 

---

 

[통과]

 

어려운 듯 풀만한 듯 나에게 적당한 난이도 같은듯.?

푸는데 30분정도 걸림