[백준/파이썬][Gold IV] 암벽 등반 - 2412

[Gold IV] 암벽 등반 - 2412

문제 링크

성능 요약

메모리: 120760 KB, 시간: 248 ms

분류

너비 우선 탐색, 자료 구조, 그래프 이론, 그래프 탐색, 해시를 사용한 집합과 맵

제출 일자

2024년 12월 26일 23:59:53

문제 설명

어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.

현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.

입력

첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.

출력

첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.

풀이

from collections import deque


def bfs(si, sj, graph, T):
    """
    너비 우선 탐색(BFS)을 사용하여 시작점에서 목표 지점까지의 최단 거리를 찾는 함수
    si, sj: 시작점의 좌표
    graph: 이동 가능한 좌표들의 집합
    T: 목표 지점의 j좌표
    반환값: 목표 지점까지의 최단 이동 횟수 또는 도달 불가능할 경우 -1
    """
    # 큐 초기화 및 시작점 추가
    # (i좌표, j좌표, 이동 횟수)를 튜플로 저장
    q = deque()
    q.append((si, sj, 0))       # si, sj, cnt
    visited = set()  # 방문한 좌표 관리
    visited.add((si, sj))

    while q:
        ci, cj, cnt = q.popleft()

        # 목표 지점 도달 시 이동 횟수 반환
        if cj == T:
            return cnt

        # 상하좌우 및 대각선을 포함한 주변 25개 칸 탐색
        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci + di, cj + dj

                # 이동 가능한 좌표이고 방문하지 않은 경우
                if (ni, nj) in graph and (ni, nj) not in visited:
                    q.append((ni, nj, cnt + 1))
                    visited.add((ni, nj))  # 방문 처리

    # 목표 지점에 도달할 수 없는 경우
    return -1


# 입력 받기
n, T = map(int, input().split())
graph = set(tuple(map(int, input().split())) for _ in range(n))

# BFS 실행 및 결과 출력
res = bfs(0, 0, graph, T)
print(res)

코드 분석

1. BFS 함수

• 입력 인자
  • si, sj: 시작점의 좌표 (0, 0).
  • graph: 이동 가능한 좌표들의 집합.
• 로직
  • deque를 사용하여 BFS 탐색을 수행합니다.
  • 현재 탐색 중인 좌표와 이동 횟수를 큐에서 꺼냅니다.
  • 목표 지점 T에 도달했는지 확인합니다.
  • 현재 위치를 기준으로 상하좌우 및 대각선을 포함한 25개의 주변 칸을 탐색합니다.
  • 이동 가능한 좌표(graph에 있는 좌표)에 대해 큐에 추가하고, 중복 방문을 방지하기 위해 visited에 해당 좌표를 저장하였음.
• 반환값
  • 목표 지점 T에 도달하면 이동 횟수를 반환.
  • 모든 탐색을 마쳤음에도 도달하지 못하면 -1 반환.

2. 입력 처리

• 사용자로부터 이동 가능한 좌표 개수(n)와 목표 지점의 y축 좌표(T)를 입력받습니다.
• 이후 n개의 좌표를 집합(set)으로 저장합니다.
  • 장점: 집합을 사용하면 좌표의 존재 여부를 O(1) 시간에 확인 가능.

3. BFS 실행 및 결과 출력

• BFS 함수를 호출하여 결과를 출력합니다.

---

장점

1. 효율적인 자료구조 사용
   • 집합(set)을 활용해 이동 가능한 좌표를 관리함으로써 좌표의 탐색 및 제거를 빠르게 수행합니다.
2. BFS를 통한 최단 경로 탐색
   • BFS는 최단 경로 탐색에 적합하며, 이동 횟수를 정확히 계산합니다.
3. 범용적인 탐색
   • 상하좌우 및 대각선을 포함한 총 25개의 칸을 탐색하여 이동 가능성을 극대화합니다.