[백준/Python] 7562번(그래프, BFS)_나이트의 이동

📌문제 유형

그래프 이론, 그래프 탐색, BFS(실버1)

 

📌문제

7562번: 나이트의 이동

 

📌나의 문제풀이

from collections import deque

t = int(input())

for _ in range(t):
    l = int(input())
    maps = [[0 for _ in range(l)] for _ in range(l)]
    s_x, s_y = map(int,input().split())
    e_x, e_y = map(int,input().split())

    q = deque()
    q.append([s_x, s_y])
    maps[s_x][s_y] = 1
    cnt = 0

    while q:
        x, y = q.popleft()

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

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l:
                if maps[nx][ny] == 0:
                    q.append([nx,ny])
                    maps[nx][ny] = maps[x][y] + 1
    print(maps[e_x][e_y] - 1)

 

📌 다른사람의 문제풀이

[python] 7562번 - 나이트의 이동

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

t = int(input().rstrip())


def bfs() :
    dx = [-1, 1, 2, 2, 1, -1, -2, -2]
    dy = [2, 2, 1, -1, -2, -2, -1, 1]

    q = deque()
    q.append((startX, startY))
    while q :
        x, y = q.popleft()
        if x == endX and y == endY :
            return matrix[x][y] -1 
        for i in range(8) :
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<l and 0<=ny<l and matrix[nx][ny] == 0 :
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx,ny))
                
            
        
for _ in range(t) :
    l = int(input().rstrip())
    startX, startY = map(int, input().rstrip().split())
    endX, endY = map(int, input().rstrip().split())
    matrix = [[0]*l for _ in range(l)]
    matrix[startX][startY] = 1
    print(bfs())

 

📌 리뷰 

- BFS는 '현재 그래프 값 + 1'로 만들어서 탐색하는 경우가 많다는 것을 잊지말기!

- maps[nx][ny] + 1을 답지 설명보고 깨달음...!