[Python/Baekjoon] 7562. 나이트의 이동

문제

1. 문제 난이도: 백준 실버 1

2. 문제 요약:

3. 문제 핵심: BFS(최소 몇 번만에 이동할 수 있는지 = 최단거리)

내 코드

def bfs(start, end, l, testCase):
    if start == end:
        return 0
    queue = deque()
    queue.append(start)
    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx<0 or nx>= l or ny<0 or ny>=l:
                continue
            if graph[testCase][nx][ny] == -1:
                graph[testCase][nx][ny] = graph[testCase][x][y] +1
                queue.append((nx, ny))
    return graph[testCase][end[0]][end[1]]+1

from collections import deque

graph = dict()
position = dict()
testCaseNum = int(input())
for i in range(testCaseNum):
    length = int(input())
    graph[i] = [[-1] * length for _ in range(length)]
    src = tuple(map(int, input().split(' ')))
    dst = tuple(map(int, input().split(' ')))
    position[i] = [src, dst]

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

for i in range(testCaseNum):
    print(bfs(position[i][0], position[i][1], len(graph[i]), i))
            

이상 코드 참고 후, 내 코드

def bfs(start, end, l):
    if start == end:
        return 0
    queue = deque()
    queue.append(start)
    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx<0 or nx>= l or ny<0 or ny>=l:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] +1
                queue.append((nx, ny))
    return graph[end[0]][end[1]]

from collections import deque
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]
testCaseNum = int(input())
graph = []
for i in range(testCaseNum):
    length = int(input())
    graph = [[0] * length for _ in range(length)]
    src = tuple(map(int, input().split(' ')))
    dst = tuple(map(int, input().split(' ')))
    print(bfs(src, dst, length))
            

배운 점

• 입력받으면서 출력도 가능
• 메모리 절약 가능(배열 적게 만들어도 됨)