나이트의 이동

가장 빠른 경로를 찾는 방법: BFS
나이트의 이동경로: 8개

문제가 발생한 코드

# 가장 가까운: BFS
from collections import deque
import sys

tc = int(input())
# dx 상하 dy 좌우
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
answer = []


def bfs():
    # 
    global flag, size

    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # print("hm", nx, ny)
            if nx <= -1 or nx >= size or ny <= -1 or ny >= size:
                break
        
            if graph[nx][ny] == 0 and visited[nx][ny] == False:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])
                visited[nx][ny] = True

            if nx == dest[0] and ny == dest[1]:
                flag = True
                break
        if flag:
            break

for i in range(tc):
    size = int(sys.stdin.readline())
    graph = [[0 for i in range(size)] for j in range(size)]
    queue = deque([list(map(int, sys.stdin.readline().split()))])
    dest = list(map(int, sys.stdin.readline().split()))
    visited = [[False for i in range(size)] for j in range(size)]

    flag = False
    if queue[0] == dest:
        answer.append(0)
    else:
        bfs()
        answer.append(graph[dest[0]][dest[1]])

print("\n".join(list(map(str, answer))))

실수

범위를 벗어나면 다음 경로를 탐색해야되는데 break를 써버려서 경로를 skip해버려서 발생한 에러.

break를 continue로 바꾸어 for 루프를 탈출하기보다 다음 루프로 넘어가야 한다.

해답

# 가장 가까운: BFS
from collections import deque
import sys

tc = int(input())
# dx 상하 dy 좌우
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
answer = []


def bfs():
    # global 변수인 flag와 size
    global flag, size

    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # print("hm", nx, ny)
            if nx <= -1 or nx >= size or ny <= -1 or ny >= size:
                #break
                continue
        
            if graph[nx][ny] == 0 and visited[nx][ny] == False:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])
                visited[nx][ny] = True

            if nx == dest[0] and ny == dest[1]:
                flag = True
                break
        if flag:
            break

for i in range(tc):
    size = int(sys.stdin.readline())
    graph = [[0 for i in range(size)] for j in range(size)]
    queue = deque([list(map(int, sys.stdin.readline().split()))])
    dest = list(map(int, sys.stdin.readline().split()))
    visited = [[False for i in range(size)] for j in range(size)]

    flag = False
    if queue[0] == dest:
        answer.append(0)
    else:
        bfs()
        answer.append(graph[dest[0]][dest[1]])

print("\n".join(list(map(str, answer))))

참고

flag는 없어도 작동은 하지만 flag를 넣은 이유는, 원하는 목적지에 다달으면 뒤에 더이어서 탐색하지 않아도 되게끔 하기 위해 추가한 코드이다.

백준에서 결과를 비교하면 392ms, 528ms보다 더 빠르게 실행되었다.