백준/ Silver 1 문제 , 백준 파이썬 7562, 안전 영역 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 7562, 안전 영역 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
최단거리는 BFS

 

 

<문제 출처>

 

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

7562번: 나이트의 이동

------------------------------------------------------------------------------------------------------------------------------

 

 

도착 지점에 -1을 심어두고 -1을 찾아 bfs를 돌리면 된다.

 

한 칸에서 움직일 수 있는 방법은 총 8가지이므로 한 칸당 총 8번의 위치를 확인한 뒤 이동시켜주면된다.

 

이때 이동하려는 곳에 이미 숫자가 부여된 곳은 이미 최단 거리가 측정된 곳으로 값을 또 변경시켜줄 필요가 없다.

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

from collections import deque

vertical=[1,2,2,1,-1,-2,-2,-1]
parallel=[-2,-1,1,2,2,1,-1,-2]
for _ in range(int(input())):
    dq=deque()
    N=int(input())
    chess=[[0 for _ in range(N)] for _ in range(N)]
    for i in range(2):
        a,b=map(int,input().split())
        if i==0:
            dq.append([a,b])
        else:
            chess[a][b]=-1
    if dq[0]==[a,b]:
        print(0)
    else:
        check=False
        while dq:
            x,y=dq.popleft()
            for i in range(8):
                move_x=x+vertical[i]
                move_y=y+parallel[i]
                if 0<=move_x<N and 0<=move_y<N:
                    if chess[move_x][move_y]==0:
                        dq.append([move_x, move_y])
                        chess[move_x][move_y]=chess[x][y]+1
                    if chess[move_x][move_y]==-1:
                        print(chess[x][y]+1)
                        check=True
                        break
            if check==True:
                break