[16948] 데스 나이트 In python

 

 

> bfs 문제

 

최소 경로를 출력해야한다길래

max로 매번 경로횟수를 체크해줘야하나

생각했으나

 

1칸씩 이동할때마다

+1씩 증가시키고

도착점에 도착하면

현재 횟수를 출력한다. 

 

 

큐에 cnt 횟수까지 넣으면

메모리초과 남..

 

 

from collections import deque

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
# 1~6번 순으로
dx = [-2, 0, 2, 2, 0, -2]
dy = [1, 2, 1, -1, -2, -1]


def bfs():
    queue = deque()
    queue.append((r1, c1, 1))
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[r1][c1] = True
    result = 10 ** 9
    while queue:
        r, c, cnt = queue.popleft()
        visited[r][c] = True
        for i in range(6):
            nr = r + dx[i]
            nc = c + dy[i]
            if 0 <= nr < n and 0 <= nc < n:
                if nr == r2 and nc == c2:
                    result = min(result, cnt)
                    break
                if not visited[nr][nc]:
                    queue.append((nr, nc, cnt + 1))
    return result


result = bfs()
if result != 10 ** 9:
    print(result)
else:
    print(-1)

 

 

따라서

cnt를 담는 배열을 하나 따로 만들어주었음

from collections import deque

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
# 1~6번 순으로
dx = [-2, 0, 2, 2, 0, -2]
dy = [1, 2, 1, -1, -2, -1]


def bfs():
    queue = deque()
    queue.append((r1, c1))
    cntArr = [[-1 for _ in range(n)] for _ in range(n)]
    cntArr[r1][c1] = 0
    while queue:
        r, c = queue.popleft()
        for i in range(6):
            nr = r + dx[i]
            nc = c + dy[i]
            if 0 <= nr < n and 0 <= nc < n:
                if cntArr[nr][nc] == -1:
                    queue.append((nr, nc))
                    cntArr[nr][nc] = cntArr[r][c] + 1

    return cntArr[r2][c2]

result = bfs()
if result != 10 ** 9:
    print(result)
else:
    print(-1)