ABOUT ME

Today
Yesterday
Total
  • [백준] 16948번 데스 나이트(python)
    Python/BAEKJOON 2022. 2. 22. 02:11
    728x90

    문제)

     

     

    알고리즘)

    -  나이트의 시작 위치를 시작으로 이동가능한 범위내에서 탐색

    - 탐색과중에서 처음 가는 위치(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
Designed by Tistory.