Chap 17. 최단경로 - Q40. 숨바꼭질

  • 0
  • 0
0
0

1. 숨바꼭질

  • 난이도
  • 풀이 시간
    • 40분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB
  • 출처
    • USACO

A. 📜 문제

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결한다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어진다.

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단한다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미한다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하라

a. 입력 조건
  • 첫째 줄에는 N, M이 주어지며, 공백으로 구분한다.
    • 2 <= N <= 20,000
    • 1 <= M <= 50,000
  • 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어진다.
    • 1 <= A, B <= N
c. 출력 조건
  1. 숨어야 하는 헛간 번호
    • 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력
  2. 그 헛간까지의 거리
  3. 그 헛간과 같은 거리를 갖는 헛간의 개수
d. 테스트 케이스
  • 입력 예시

    
    6 7
    3 6
    4 3
    3 2
    1 3
    1 2
    2 4
    5 2
    
    
  • 출력 예시

    
    4 2 3
    
    

B. 💡 내 답안

a. 😊 1차 시도 (성공)

"""
Date    : 2021.11.26
Update  : 2021.11.26
Source  : Q40_숨바꼭질.py
Purpose : 다익스트라 알고리즘을 활용하여 1번 헛간에서 가장 멀리 있는 헛간을 구한다.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
import heapq

# 헛간 수, 헛간 통로의 수
n, m = list(map(int, input().split()))

# 인접 리스트로 헛간 통로를 입력받음
graph = [[] for i in range(n+1)]

# 헛간은 양방향 통로가 존재한다고 명시되어 있으므로, A -> B, B -> A 모두 인접 리스트에 입력함.
for _ in range(m):
    start, end = list(map(int, input().split()))

    graph[start].append(end)
    graph[end].append(start)

# 최단거리를 업데이트하는 리스트를 만듬.
# 최단거리를 구하는 것이기 때문에, 초기값은 양의 무한대를 줌
distance = [1e9 for i in range(n+1)]
# 처음 시작하는 위치의 최단거리는 0으로 줌
distance[1] = 0

# 힙으로 사용할 q 생성
q = []
# q에는 현재까지의 최단거리와 해당 노드 번호를 입력함.
heapq.heappush(q, (distance[1], 1))

while q:
    dist, node = heapq.heappop(q)

    # 현재까지의 최단거리가 최단거리 리스트에 있는 값보다 크다면, 최단거리가 아니므로 반복문의 시작으로 돌아감
    if dist > distance[node]:
        continue

    # 현재 노드와 연결된 노드들을 탐색
    for next_node in graph[node]:
        # 각 노드 사이의 거리는 무조건 1
        # 노드 사이의 거리를 비용으로 생각하지 않고, 횟수로 생각하기 때문.
        next_node_dist = 1
        cost = dist + next_node_dist

        # 현재 노드와 다음 노드의 비용(거리)를 더했을 때, 최단 거리보다 작다면 교체함.
        if cost < distance[next_node]:
            distance[next_node] = cost
            heapq.heappush(q, (distance[next_node], next_node))

# 번호, 거리, 같은 거리 개수
result = [0, 0, 0]

for i in range(1, n+1):
    # distance를 node가 작은 순서대로 탐색하면서, 최단 거리가 긴 node를 발견하면 값(노드 번호, 거리, 같은 거리 횟수)을 전부 교체
    if result[1] < distance[i]:
        result = [i, distance[i], 1]
    # 최단 거리가 가장 긴 노드와 같은 최단 거리를 가지는 노드가 존재하면, 같은 거리 갯수를 증가.
    elif result[1] == distance[i]:
        result[2] += 1

print(*result, sep=' ')

c. 🙄 회고

내 풀이

  • 최단 거리를 구하고 최단 거리가 가장 큰 헛간을 찾는 문제다.
  • 헛간의 출발지점이 정해져 있어서, 다익스트라 알고리즘을 사용해야겠다고 생각했다.
  • 양방향 통로이기 때문에 A -> B, B -> A를 인접 리스트에 입력했다.
  • 가장 멀리 있는 헛간을 출력하기 위해 for문을 돌려서 save값과 비교하며 갱신해주었다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.