파이썬 백준 7562번 나이트의 이동 나이트를 목적지까지 이동시키는 문제

  문제

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

  입력

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

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

  출력

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

  풀이

from collections import deque

dx=[-1,-2,-2,-1,1,2,2,1]
dy=[2,1,-1,-2,-2,-1,1,2]

n=int(input())

for i in range(n):
    l=int(input())
    graph=[]
    for i in range(l):
        graph.append([0]*l)
    queue=deque()
    x,y=map(int,input().split())
    w,z=map(int,input().split())
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        if x==w and y==z:
            break
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=l or ny>=l:
                continue
            if graph[nx][ny]==0:
                graph[nx][ny]=graph[x][y]+1
                queue.append((nx,ny))
    print(graph[w][z])

from collections import deque

BFS는 First in First out 구조로, deque 자료구조를 사용한다. 따라서 deque를 import하도록 한다.

 

dx=[-1,-2,-2,-1,1,2,2,1]
dy=[2,1,-1,-2,-2,-1,1,2]

나이트의 '이동 방향'을 미리 입력 해 준다. 해당 리스트는 현재 위치에서 다른 위치로 이동할 위치를 구할 때 사용될 예정이다.

 

n=int(input())

테스트 케이스의 개수를 입력 받는다.

 

- 아래는 deque로 dfs를 수행하기 전 사전 작업이다.

for i in range(n):

테스트 케이스만큼을 반복할 수 있도록 for문 range에 n값을 넣는다.

    graph=[]

    l=int(input())

graph는 체스판을 의미한다고 보면 된다. 2차원 리스트를 통해 체스판을 구현할 것이다.

또한 이 값에는 몇 회 이동하였는지 횟수가 적히게 된다.

l은 체스판의 크기에 사용될 값을 입력 받는 데 사용된다.

    for i in range(l):

        graph.append([0]*l)

lxl 체스판이기 때문에 [0]*l만큼의 열을 각 행마다 l번 추가한다.

    queue=deque()

    x,y=map(int,input().split())

    w,z=map(int(input().split())

    queue.append((x,y))

queue에 deque()를 선언한다.

x,y에 '시작 위치'를 처음에 입력 해 준다.

w,z에 '목표 위치'를 설정 해 준다.

queue.append((x,y))로 위에서 입력된 '시작 위치'를 넣어준다.

 

while queue:

while queue: 는 bfs의 개념에서 나온다. bfs는 탐색 노드를 큐에 삽입하고 방문 처리 후, 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 바운하지 않은 노드를 모두 큐에 삽입하는 것이다. 따라서 수행할 수 없을 때까지 반복한다는 점에서 queue 내에 아무 것도 남아있지 않으면 while문을 종료한다.

    x,y=queue.popleft()

        if x==w and y==z:

        break

.popleft() 가장 처음 입력된 좌표를 꺼낸 후 x,y 현재 위치에 매핑한다. 이 때 w,z와 비교하여 목표 위치에 도달 해 있다면 while 문을 종료한다. (시간 초과를 피하기 위해서 굉장히 중요하다.)

    for i in range(8):

        nx=x+dx[i]

        ny=y+dy[i]

현재 위치를 기준으로 8방향 모두 구하게 된다. 따라서 위에서 정해 두었던 이동 값을 가져와, 현재값+이동값으로 신규 위치를 구한다.

 

        if nx<0 or ny<0 or nx>=l or ny>=l:

                continue

        if graph[nx][ny]==0:

            graph[nx][ny]=graph[x][y]+1

            queue.append((nx,ny))

    print(graph[w][z])

신규 위치가 적합한 지 검토하는 시간을 가지고, 적합하지 않으면 버려야 한다.

우선 nx의 범위를 정하여 체스판 내 범위에 있는 지 확인한다.

 

한번도 방문하지 않은 곳이라면, 현재위치까지의 이동 횟수에 이제 신규 좌표로 이동할 것이기 때문에 +1을 더한 값을 신규 좌표값에 넣어준다.

이후 w,z 좌표에서의 값을 print(graph[w][z])로 하여 출력한다.

 

  오답노트

- '시작 위치'를 '계산 이후'에도 사용하려면, 시작 위치를 입력받자마자 다른 변수에 저장 해 두어야 한다.

이유는 계산 과정이 진행 되면서 x,y 값은 계속해서 변경될 것이기 때문이다.

- 아래 조건은 시간 초과를 피하기 위해서 반드시 필요하다.

'현재 위치'가 '목표 위치'에 도달하는 순간 while문을 멈춘다. 이 조건이 없는 경우 그래프의 모든 경우의 수를 구하는 것이므로 불필요한 연산이 늘어나게 된다.

        if x==w and y==z:

        break