[백준/Python] 13424번 : 비밀 모임

2025. 2. 22. 22:12· Koala - 17기/코딩테스트 심화 스터디
목차
  1. 입력
  2. 출력
  3. 문제 코드

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로 비밀통로를 이용해서 갈 수 없는 경우는 존재하지 않으며, 같은 비밀통로에 대한 정보가 중복되어 주어지지 않는다. 비밀통로의 정보가 모두 주어진 다음 그 다음 줄에 모임에 참여하는 친구의 수 K(1 ≤ K ≤ N)가 주어진다. 각 테스트 케이스의 마지막 줄에는 모임에 참여하는 친구들이 현재 위치해 있는 방의 번호 K개가 공백으로 구분되어 주어진다. 친구들이 있는 방은 항상 N개의 방 중 하나이며, 방 번호가 중복되는 경우는 없다. 즉, 두 명 이상이 한 방에 있는 경우는 입력으로 주어지지 않는다. 

 

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 1줄에 1개씩 출력한다. 각 테스트 케이스마다 모임에 참여하는 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소의 방 번호를 출력한다. 만약 그러한 장소가 여러 개일 경우, 그중 번호가 가장 작은 방의 번호를 출력한다.

문제 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start, n, graph):
    distance = [INF] * (n + 1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for next, n_dist in graph[now]:
            cost = dist + n_dist
            if cost < distance[next]:
                distance[next] = cost
                heapq.heappush(q, (cost, next))
                
    return distance

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    K = int(input())
    students = list(map(int, input().split()))
    
    total_distances = [0] * (N + 1)
    for student in students:
        distances = dijkstra(student, N, graph)
        for i in range(1, N + 1):
            total_distances[i] += distances[i]
    
    min_dist = INF
    answer = 1
    for room in range(1, N + 1):
        if total_distances[room] < min_dist:
            min_dist = total_distances[room]
            answer = room
            
    print(answer)

 

문제 해설

 

1. 각 학생들의 위치에서 모든 방까지의 최단 거리를 다익스트라 알고리즘으로 계산

2. 각 방마다 모든 학생들의 이동거리 합계(total_distance)를 구함

3-1. total_distance가 최소가 되는 방 번호를 찾아 출력

3-2. 여러 개인 경우 가장 작은 방 번호 선택

 

저작자표시 (새창열림)

'Koala - 17기 > 코딩테스트 심화 스터디' 카테고리의 다른 글

[BOJ/Python3] 5972번 : 택배 배송  (0) 2025.02.23
[백준/Python] 1504 특정한 최단 경로  (0) 2025.02.23
[백준/자바] 4485. 녹색 옷 입은 애가 젤다지?  (0) 2025.02.17
[백준/Python] 2644번 : 촌수 계산  (0) 2025.02.16
[백준/Python] 2583번 : 영역 구하기  (0) 2025.02.16
  1. 입력
  2. 출력
  3. 문제 코드
'Koala - 17기/코딩테스트 심화 스터디' 카테고리의 다른 글
  • [BOJ/Python3] 5972번 : 택배 배송
  • [백준/Python] 1504 특정한 최단 경로
  • [백준/자바] 4485. 녹색 옷 입은 애가 젤다지?
  • [백준/Python] 2644번 : 촌수 계산
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1883)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • 파이썬
  • dfs
  • 백트래킹
  • 백준
  • C++
  • dp
  • BOJ
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/Python] 13424번 : 비밀 모임
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.