백준_7562 (나이트의 이동_BFS 최단경로_중요)

최단경로 제일 중요한 것

• BFS 진행하면서, 내가 원하는 goal 위치에 도달하면 +1해서 바로 출력하고 return 해버려

if ny == goal[0] and nx == goal[1]:         # (제일 중요!!!!!!) 최단경로
   print(graph[ny][nx])                     # (중요) 바로 출력해버려
   return                                   # (중요) 그리고 끝내버려

---

• 링크 : https://www.acmicpc.net/problem/7562
  
  

---

메모한 것 (핵중요)

• 전에 동빈나에서 나왔던 유형인 것 같은데

• 다른 점은 아마 한 변의 길이를 받는게 없었던듯? 어쨌든 똑같다

• 일단 BFS 최단경로 방식으로 풀어나가면 될거같은데

  • 그 숨바꼭질 문제(백준 1697)

1. 변의 길이만큼 n x n graph 만든다 (이때 다 0으로 초기화 => 이동할 때마다 가중치 부여)
2. 갈 수 있는 모든 경우의 수에 대해 que에 넣고 bfs 돌린다
3. bfs 진행 시 ny, nx에는 prev_y와 prev_x에 +1한 값을 넣어주다가
4. (핵중요) 이동할 위치의 인덱스 == 목표 인덱스 이면 print(이동 횟수) 후 break

---

바로 풀었음 (백준 1697 참고했음)

''' 내가 푼 - 백준 1697을 참고하여 (바로 풀었음) '''
from collections import deque

def bfs(L, now, goal, graph):
    answer = 0
    que = deque([now])
    # 체스의 특성대로 이동
    dy = [-2, -1, 1, 2, 2, 1, -1, -2]
    dx = [-1, -2, -2, -1, 1, 2, 2, 1]
    
    while que:
        prev_y, prev_x = que.popleft()
        for i in range(8):
            ny = prev_y + dy[i]
            nx = prev_x + dx[i]
            
            if 0 <= ny < L and 0 <= nx < L and graph[ny][nx] == 0:
                graph[ny][nx] = graph[prev_y][prev_x] + 1
                que.append([ny, nx])
                
            if ny == goal[0] and nx == goal[1]:   # (제일 중요!!!!!!) 최단경로
                print(graph[ny][nx])               # (중요) 바로 출력해버려
                return                            # (중요) 그리고 끝내버려

for _ in range(int(input())):
    L = int(input())
    now = list(map(int,input().split()))
    goal = list(map(int,input().split()))
    
    graph = [[0] * L for _ in range(L)]
    
    if now == goal:
        print(0)
    else:
        bfs(L, now, goal, graph)