99클럽 코테 스터디 9일차 TIL + BFS

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

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

dx = [1,2,2,1,-1,-2,-2,-1]
dy = [2,1,-1,-2,-2,-1,1,2]
n = int(input())

def bfs(x,y,moveX,moveY):
    que = deque()
    que.append([x,y])
    #graph[x][y] = 1
    while que:
        a, b = que.popleft()

        if a == moveX and b == moveY:
            return graph[a][b]
        for i in range(8):
            nx = a + dx[i]
            ny = b + dy[i]

            if nx < 0 or nx >= l or ny < 0 or ny >= l:
                continue
            if graph[nx][ny] == 0:
                que.append([nx,ny])
                graph[nx][ny] = graph[a][b] + 1


for _ in range(n):
    l = int(input())
    graph = [[0] * l for _ in range(l)]

    x, y = map(int, input().split())
    moveX, moveY = map(int, input().split())

    if x == moveX and y == moveY:
        print(0)
        continue

    answer = bfs(x, y, moveX, moveY)
    print(answer)

• 문제에서 최소 몇 번만에 목적지로 이동할 수 있는지 물었고 bfs를 떠올렸다.
• 처음에는 visitied 리스트를 생각했지만, graph리스트 하나만으로 값이 0인지 아닌지로 방문여부로 따질 수 있었다.
• graph의 값으로 이동할 때마다 이전 값에 +1 을 해준다.
• 처음 bfs를 시작할 때 시작점을 방문표시 해준다면 (graph[x][y] = 1) 1로 시작했기 때문에 목적지에 도달했을 때 graph[a][b]-1 값을 해주어야한다.
• 처음 que를 선언할 때 , que = deque() 후에 append로 값을 넣어주자 !  que = deque([x,y]) 로 하면 "cannot unpack non-iterable int object" 에러가 나는거 같다....~