접근
미로찾기와 동일하지만 그 이동이 위, 아래, 왼쪽, 오른쪽 4방향이 아니라 사진에 나와있는 것과 같이 나이트가 이동할 수 있는 8방향을 다음 탐색에 추가해주면 된다.
BFS를 이용한 미로찾기 참고 링크: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)
코드
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())
더 생각해 볼 것?
...
코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!
반응형
'코딩 > 백준 (Python)' 카테고리의 다른 글
백준 1753번: 최단경로 (Python) (0) | 2021.04.14 |
---|---|
백준 1707번: 이분 그래프 (Python) (0) | 2021.04.14 |
백준 1697번: 숨바꼭질 (Python) (0) | 2021.04.12 |
백준 7569번: 토마토 (Python) (0) | 2021.04.11 |
백준 7576번: 토마토 (Python) (0) | 2021.04.11 |
최근댓글