[백준 알고리즘] 14618번: 총깡 총깡 (Python)

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

14618번: 총깡 총깡

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra1():
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  for x in A: # A형 집들 중에서 진서집까지의 최단거리 구하기
    min_dis[x] = 0
    hq.heappush(q,[0,x])
  
  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > cur_dis + next_dis:
        min_dis[next_node] = cur_dis + next_dis
        hq.heappush(q,[cur_dis+next_dis,next_node])
  return min_dis

def dijkstra2():
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  for x in B: # B형 집들 중에서 진서집까지의 최단거리 구하기
    min_dis[x] = 0
    hq.heappush(q,[0,x])
  
  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > cur_dis + next_dis:
        min_dis[next_node] = cur_dis + next_dis
        hq.heappush(q,[cur_dis+next_dis,next_node])

  return min_dis

n,m = map(int,input().split())
graph = [[]for _ in range(n+1)]
j = int(input())
k = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
for _ in range(m):
  x,y,z = map(int,input().split())
  graph[x].append([y,z])
  graph[y].append([x,z])

first = dijkstra1()
second = dijkstra2()
a = first[j]
b = second[j]
# 비교해서 답 출력하기
if a != float('inf') and b != float('inf'):
  if a <= b:
    print('A')
    print(a)
  else:
    print('B')
    print(b)

elif a == float('inf') and b != float('inf'):
  print('B')
  print(b)

elif a != float('inf') and b == float('inf'):
  print('A')
  print(a)

elif a == float('inf') and b == float('inf'):
  print(-1)

 

풀이

★ 문제 설명이 꽤나 어렵게 되어있어 헷갈렸는데, 난이도가 골드 3이기도 했고, A형 집과 B형 집 중에서 진서의 집과 가장 가까운 집이 어떤 형의 집인가만 알면되는 문제라고 생각하고 풀었습니다 ! 

 

★ 다익스트라 함수를 총 2개 만들었고, 각 함수마다 A형 집, B형 집을 우선순위 큐에 한번에 넣어 진서의 집까지의 최단 거리를 구해줬습니다.

 

★ 그 후 최단거리 비교를 통해 a형의 집이 b형의 집보다 더 가깝거나 같은 경우 A형집을 출력하고, 반대의 경우 B형 집을 출력해줬습니다 :)