[Python][백준] 7562. 나이트의 이동/ BFS,그래프 탐색(S1)

링크🔗

https://www.acmicpc.net/problem/7562

---

🗒️파이썬 코드 풀이

from collections import deque

T = int(input())
for _ in range(T):
    I = int(input())
    start_x,start_y = list(map(int,input().split()))
    end_x,end_y = list(map(int,input().split()))
    chess = [[-1]*I for _ in range(I)]

    nights = [[-2,-1],[-2,1],[2,1],[2,-1],[-1,2],[1,2],[-1,-2],[1,-2]]

    def dfs(i,j):
        q = deque([[i,j]])
        chess[i][j] = 0 
        while q :
            v = q.popleft()
            for night in nights:
                ni,nj = v[0]+night[0],v[1]+night[1]
                if 0<=ni<I and 0<=nj<I:
                    if chess[ni][nj] == -1 :
                        chess[ni][nj] = chess[v[0]][v[1]] + 1
                        q.append([ni,nj])

    dfs(start_x,start_y)
    print(chess[end_x][end_y])

 

1. 이런 최단 경로를 찾는 문제에서는 Queue를 이용한 BFS 방식을 사용해야한다.

(DFS로 풀 경우 최소의 수로 빠져나올 수 없다.)

DFS는 한명을 끝까지 박살내어, 결국 전체를 박살내는 느낌
BFS는 여러 명을  골고루 때리면서, 결국 전체를 박살내는 느낌

 

2. 체스판에 방문 여부를 확인하기 위해, chess 리스트 만들었다. 

 

3. nights 리스트에서 에서 나이트의 가능한 이동 범위를 모두 나타낸다. 

 

4. BFS 함수를 시작 좌표를 매개변수로 주어 실행하면 된다.

BFS 함수 패턴은 간단하다.
Queue를 만들어주고, 하나씩 빼면서 유효성을 검사한다. 
그리고 유효하면 새로운 값을 추가하고 Queue에 다음 변수를 넣어준다.
이 과정은 Queue가 완전히 비워질 때까지 해주면 된다.

 

5. BFS 함수가 종료되면, 시작 좌표 기준으로 chess 판이 만들어지고,

내가 원하는 끝 좌표를 출력하면 된다. 

 

 

📌  문제 코멘트

DFS와 BFS 문제를 좀 풀면 그다지 어려운 문제가 아니다.

예전이 이런 비슷한 문제를 코테에서 틀렸던 것 같다. 

그래도 이제 이런 비슷한 문제가 나오면 풀 수 있을 것 같다.

---

📚문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0