-
[백준] 16948번 데스 나이트(python)Python/BAEKJOON 2022. 2. 22. 02:11728x90
문제)
알고리즘)
- 나이트의 시작 위치를 시작으로 이동가능한 범위내에서 탐색
- 탐색과중에서 처음 가는 위치(graph 값이 0인 위치) q에 추가
- 이동한 위치의 값(graph[fin_x][fin_y])은 이전 값(graph[x][y])에 +1 즉 이동 횟수를 표기
- 모든 과정을 탐색하는 도중 fin_x, fin_y가 q에 있다면
return graph[fin_x][fin_y]
코드)
#데스 나이트 import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque() graph = [[0]*n for _ in range(n)] knight_x, knight_y, fin_x, fin_y = map(int, input().split()) #데스나이트 출발지점과 도착지점 move_x = [-2, 0, 2 ,2, 0, -2] move_y = [-1, -2 ,-1, 1, 2, 1] def bfs(x, y): q.append([x, y]) while q: x, y = q.popleft() for a in range(6): #데스나이트의 예상이동 위치 test_x = x + move_x[a] test_y = y + move_y[a] if 0 <= test_x < n and 0 <= test_y < n and graph[test_x][test_y] == 0: #1. test_x, test_y가 그래프범위 2. 방문한적이 없는 위치 graph[test_x][test_y] = graph[x][y] + 1 #이동하기전 위치 값 +1 q.append([test_x, test_y]) else: continue if [fin_x, fin_y] in q: #해당 위치에 도착 return graph[fin_x][fin_y] #모든 탐색 후 값이 없다면 return -1 result = bfs(knight_x, knight_y) print(result)
728x90'Python > BAEKJOON' 카테고리의 다른 글
[백준] 9048번 동전(python) (0) 2022.03.10 [백준] 2346번 풍선 터트리기(python) (0) 2022.02.28 [백준] 2304번 창고 다각형(python) (0) 2022.02.22 [백준] 3036번 링(python) (0) 2022.02.15 [백준] 1431번 시리얼번호(python) (0) 2022.02.15