[백준] 7562번 나이트의 이동

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

내 코드

from collections import deque

# 나이트 이동 가능한 칸
MOVABLE = [(1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)]

def bfs(I, start_q, visited):
    q = deque(start_q)
    next_q = deque([])

    while q:
        x, y = q.popleft()

        # 나이트 이동 가능시 q에 넣기
        for dx, dy in MOVABLE:
            nx, ny = x + dx, y + dy

            # 체크 판 범위 내, 방문처리 한적 없으면
            if 0 <= nx < I and 0 <= ny < I and visited[ny][nx] is False:
                visited[ny][nx] = True  # 방문처리
                next_q.append((nx, ny))

    return next_q

T = int(input())  # 테스트 케이스

for test_case in range(T):
    I = int(input())  # 한 변의 길이
    x, y = map(int, input().split())  # 시작위치
    end_x, end_y = map(int, input().split())  # 종료위치

    # 시작위치와 종료위치가 같으면 테스트 케이스 넘어감
    if (x, y) == (end_x, end_y):
        print(0)
        continue

    visited = [[False] * I for _ in range(I)]

    q = [(x, y)]  # 초기 위치
    counts = 0  # 이동횟수

    visited[y][x] = True  # 방문처리

    while True:
        next_q = bfs(I, q, visited)
        counts += 1

        # next_q 에 끝 위치 들어있는지 검사
        if (end_x, end_y) in next_q:
            print(counts)
            break

        # 이동한 위치로 q 교체
        q = next_q

chatGPT

개선 코드

내 코드가 더 빠르다.

from collections import deque

# 나이트가 이동할 수 있는 8가지 방향
MOVABLE = [(1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)]

def bfs(board_size, start, end):
    queue = deque([start])  # 시작 위치를 큐에 넣음
    visited = [[False] * board_size for _ in range(board_size)]
    visited[start[1]][start[0]] = True  # 시작 위치 방문 처리
    moves = 0  # 이동 횟수

    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()

            # 도착 위치에 도달하면 이동 횟수 반환
            if (x, y) == end:
                return moves

            # 나이트가 이동할 수 있는 모든 위치 탐색
            for dx, dy in MOVABLE:
                nx, ny = x + dx, y + dy

                # 체스판 범위 내에서 아직 방문하지 않은 위치만 탐색
                if 0 <= nx < board_size and 0 <= ny < board_size and not visited[ny][nx]:
                    visited[ny][nx] = True
                    queue.append((nx, ny))

        moves += 1  # 현재 깊이(거리)에서 탐색 완료 후 이동 횟수 증가

    return -1  # 도달할 수 없는 경우 (문제 조건에서는 발생하지 않음)

# 입력 처리 및 테스트 케이스 실행
T = int(input())  # 테스트 케이스 수

for _ in range(T):
    board_size = int(input())  # 체스판 크기
    start = tuple(map(int, input().split()))  # 시작 위치
    end = tuple(map(int, input().split()))  # 종료 위치

    # 시작 위치와 종료 위치가 같으면 0 출력
    if start == end:
        print(0)
    else:
        print(bfs(board_size, start, end))

---

개선된 점

1. bfs 함수에서 불필요한 리스트 제거
   • 기존 코드에서는 next_q라는 리스트를 생성하고 이를 반환했지만, BFS 탐색에서는 한 번의 큐를 재활용해도 충분합니다.
   • 큐를 한 번만 사용함으로써 메모리 사용량을 줄이고 코드 가독성을 높였습니다.
2. 반복 구조 단순화
   • 기존 코드에서는 이동 횟수(counts)를 BFS 외부에서 증가시켰지만, 개선 코드에서는 레벨별 탐색을 완료할 때마다 이동 횟수를 증가시키는 방식으로 간소화했습니다.
   • 이는 BFS 알고리즘의 표준적인 방식으로, 논리 구조가 더 명확해졌습니다.
3. 조건문 처리 개선
   • 도착 위치에 도달하면 탐색을 중단하고 즉시 이동 횟수를 반환합니다.
   • 기존 코드에서는 도착 여부를 매번 확인하거나 중간에 리스트에서 검색했지만, 개선된 코드에서는 탐색 중 바로 확인해 효율성을 높였습니다.
4. 방문 처리 간소화
   • 기존 코드에서는 방문 여부를 처리하는 조건이 함수 내부에 여러 번 호출되었으나, 개선된 코드에서는 한 곳에서 바로 처리해 코드 중복을 줄였습니다.
5. 코드의 역할 분리
   • 개선 코드에서는 BFS 탐색 로직과 입력 처리 및 테스트 케이스 실행을 명확히 분리했습니다.
   • 덕분에 코드의 각 부분이 수행하는 역할이 명확해졌습니다.

부가 질문

내 생각

1. 튜플에 바로 값 담는 코드 start = tuple(map(int, input().split()))
2. bfs 내부에서 이동 위치 탐색 중에 바로 도착지점 비교해서 효율을 높이자.