[TIL] 99클럽 코테 스터디 9일차 TIL - BFS/DFS :< 백준 7562 나이트의 이동> 문제 풀이 with python

Today's keyword : BFS/DFS

 

📌 문제설명

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

이 문제는 체스판에서 나이트가 특정 위치에서 다른 위치로 이동하는 최소 이동 횟수를 구하는 문제입니다. 나이트는 L자 형태로 이동할 수 있으며, 주어진 체스판의 크기와 시작 및 목표 위치가 주어졌을 때, 나이트가 목표 위치에 도달하기 위해 필요한 최소 이동 횟수를 계산해야 합니다.

• 입력 
  • 첫 번째 줄에 테스트 케이스 T가 주어집니다
  • 각 테스트 케이스마다 체스판의 크기(I), 나이트의 시작 위치, 나이트의 목표 위치가 주어집니다.
• 출력 : 각 테스트 케이스마다 나이트가 목표 위치에 도달하기 위한 최소 이동 횟수를 출력합니다. 

📌 문제풀이

from collections import deque

T = int(input())  # 테스트 케이스 수 입력
for _ in range(T):
    I = int(input())  # 체스판의 크기
    x, y = map(int, input().split())  # 시작 위치
    end_x, end_y = map(int, input().split())  # 목표 위치

    # 그래프와 방문 리스트 초기화
    graph = []
    visited = []
    for i in range(I): 
        graph.append([0] * I)  # 이동 횟수를 저장할 그래프
        visited.append([0] * I)  # 방문 여부를 저장할 리스트
        
    queue = deque()  # BFS를 위한 큐
    queue.append((x, y))  # 시작 위치 큐에 추가

    while queue: 
        x, y = queue.popleft()  # 큐에서 위치 꺼내기
        
        # 목표 위치에 도달한 경우
        if x == end_x and y == end_y: 
            print(graph[x][y])  # 이동 횟수 출력
            break
        
        # 나이트의 이동 방향
        move = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (2, -1), (1, -2)]
        for dx, dy in move: 
            nx, ny = x + dx, y + dy  # 새로운 위치 계산
            # 새로운 위치가 체스판 범위 내에 있고 방문하지 않은 경우
            if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]: 
                graph[nx][ny] = graph[x][y] + 1  # 이동 횟수 기록
                visited[nx][ny] = 1  # 방문 표시
                queue.append((nx, ny))  # 큐에 추가
                # print(queue)
                # print(*graph, sep='\n')

1. 입력 처리

• 테스트 케이스의 수 T를 입력받고, 각 테스트 케이스에 대해 체스판의 크기 I, 시작 위치 (x, y), 목표 위치 (end_x, end_y)를 입력받습니다.

2. 그래프 및 방문 리스트 초기화:

• graph와 visited 리스트를 초기화합니다. graph는 각 위치에서 나이트가 이동한 횟수를 저장하고, visited는 해당 위치를 방문했는지 여부를 기록합니다.

3. BFS 구현:

• BFS(너비 우선 탐색)를 사용하여 나이트의 이동을 탐색합니다. BFS는 최단 경로를 찾는 데 유리하므로, 나이트가 목표 위치에 도달하는 최소 이동 횟수를 찾는 데 유용합니다.
• BFS를 위해 큐를 사용하고, 시작 위치를 큐에 추가합니다.

4. 이동 가능 위치 탐색:

• 나이트의 이동 방식은 L자 형태로 문제에서 제시된 그림처럼 8가지 방향으로 이동할 수 있습니다. 각 방향에 대해 새로운 위치 (nx, ny)를 계산하고, 이 위치가 체스판의 범위 내에 있으며 방문하지 않은 경우에만 큐에 추가합니다.
• 이동 횟수를 graph[nx][ny]에 기록하고, 해당 위치를 방문했음을 visited[nx][ny]에 표시합니다.

5. 목표 위치 도달 확인:

• 큐에서 위치를 꺼내면서 목표 위치에 도달했는지 확인합니다. 목표 위치에 도달하면 이동 횟수를 출력하고, BFS를 종료합니다.

 

예시 확인

주식처리 된 print 문을 찍어보면 큐가 어떻게 쌓이고 이동횟수를 저장한 graph가 어떻게 기록되고 있는지 알 수 있습니다. I가 8이고, 시작위치가 (0, 0), 목표위치가 (7,0) 케이스에 처음 움직이는 과정은 아래와 같습니다.

 

 

📌 오늘의 회고 

BFS문제는 많이 풀어서 익숙해지고 있다. 

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL