개발 학습 블로그입니다.

2 minute read

백준 문제 중 7562번

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

문제

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

img

입력

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

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

출력

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

풀이

이전의 풀어봤던 미로찾기와 상당히 유사한 문제 이고 최단 경로를 찾아야 하므로 BFS로 접근 했다.

Try1

discovered 리스트 사용

solutuin 함수는 입력 출력을 처리하기 위한 함수이고 내부함수 _bfs를 살펴보자.

[dx[i],dy[i]] 는 각각 나이트가 이동할 수 있는 조합을 나타낸다

  • 큐를 선언하고 시작점은 cur 이므로 cur을 큐에 넣어준다.

  • 이미 방문한 노드를 표시할 discovered 리스트를 선언한다.

  • 큐가 차있는동안 반복을 시작한다.

  • 만약 v,w 이 최종 목적지인 des에 도달한다면 바로 break로 종료한다.

  • v,w에 나이트가 움직일수 있는 경우의 수인 dx,dy 를 더한 인덱스가 인덱스 범위를 벗어나지않고, 아직 방문하지 않은 노드라면 계속 진행한다.

  • 그리고 현재 경로까지의 칸을 세기위해 board[nx][ny] 는 이전 인덱스 v,w의 maze 값 즉 board[v][w]에 +1을 해준다.

from collections import deque

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

results = []

t = int(input())

def solution():
    l = int(input())

    board =[[0 for _ in range(l)]for _ in range(l)]

    cur = list(map(int,input().split()))
    des = list(map(int,input().split()))



    def _bfs():

        q = deque()
        q.append(cur)

        discovered = []

        while q:

            v,w = q.popleft()

            if v==des[0] and w==des[1]:
                results.append(board[v][w])
                break 

            for i in range(8):
                nx,ny = v+dx[i], w+dy[i]
                if 0<=nx<l and 0<=ny<l:
                    if [nx,ny] not in discovered:
                        discovered.append([nx,ny])
                        q.append([nx,ny])
                        board[nx][ny] = board[v][w] + 1

    _bfs()


for _ in range(t):
    solution()

for r in results:
    print(r)

그러나 위의 코드는 시간초과에 걸렸고 최적화가 필요했다.

Try2

board 자체로 방문여부 확인

board를 처음에 0으로 초기화 했기때문에 board가 아직 0인 인덱스는 방문하지 않음을 의미하고, 이를 discovoered 대신 사용했다.

from collections import deque

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

results = []

t = int(input())

def solution():
    l = int(input())

    board =[[0 for _ in range(l)]for _ in range(l)]

    cur = list(map(int,input().split()))
    des = list(map(int,input().split()))



    def _bfs():

        q = deque()
        q.append(cur)

        discovered = []

        while q:

            v,w = q.popleft()

            if v==des[0] and w==des[1]:
                results.append(board[v][w])
                break 

            for i in range(8):
                nx,ny = v+dx[i], w+dy[i]
                if 0<=nx<l and 0<=ny<l:
                    if board[nx][ny]==0:
                        discovered.append([nx,ny])
                        q.append([nx,ny])
                        board[nx][ny] = board[v][w] + 1

    _bfs()


for _ in range(t):
    solution()

for r in results:
    print(r)


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

Leave a comment

You may also enjoy