접근

미로찾기와 동일하지만 그 이동이 위, 아래, 왼쪽, 오른쪽 4방향이 아니라 사진에 나와있는 것과 같이 나이트가 이동할 수 있는 8방향을 다음 탐색에 추가해주면 된다.

BFS를 이용한 미로찾기 참고 링크: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)

 

백준 2178번: 미로 탐색 (Python)

접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸

ca.ramel.be

코드

import sys

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


def bfs():
    visited = [[-1] * n for __ in range(n)]
    q = []
    q.append(start)
    visited[start[0]][start[1]] = 0
    while q:
        now = q.pop(0)
        if now == end:
            return visited[now[0]][now[1]]
        for i in range(8):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:
                visited[nx][ny] = visited[now[0]][now[1]] + 1
                q.append([nx, ny])


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    start = list(map(int, sys.stdin.readline().split()))
    end = list(map(int, sys.stdin.readline().split()))
    print(bfs())

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기