[BOJ/python] 13911번 집 구하기

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

13911번: 집 구하기

 

문제 해석

 

이 문제는 다익스트라 문제로 맥세권과 스세권을 만족하는 집중 가장 최단거리를 가진 집을 구하는 문제이다.

이때 맥도날드와 스타벅스의 위치에는 집이 존재하지 않고,

한 정점에 맥도날드와 스타벅스가 동시에 존재할 수 있다.

---

코드

import heapq
input = __import__('sys').stdin.readline

# Input
n, m = map(int, input().split()) 
adj = [[] for _ in range(n + 3)] # 인접리스트 n + 3인 이유는 가상의 노드 2개 추가

# 가상의 노드 추가
macV = n + 1 
starV = n + 2

for i in range(m):
    a, b, c = map(int, input().split())
    adj[a].append([b, c])
    adj[b].append([a, c])

mac, macinHome = map(int, input().split())
macList = list(map(int, input().split()))
star, starinHome = map(int, input().split())
starList = list(map(int, input().split()))

# 가상의 노드에 연결
for i in macList:
    adj[macV].append([i, 0])
    adj[i].append([macV, 0])

for i in starList:
    adj[starV].append([i, 0])
    adj[i].append([starV, 0])

# mac -> 집의 최소경로
hq = []
cost = [float('inf')] * (n + 3)
cost[macV] = 0
heapq.heappush(hq, [0, macV])

while hq:
    t, x = heapq.heappop(hq) # t: 현재까지의 가중치, x는 현재 노드
    if cost[x] != t: continue
    for nx, nt in (adj[x]): # nx는 노드, nt는 가중치
        # 가상의 노드를 지날순 없음
        if nx == macV or nx == starV: continue

        if cost[nx] > t + nt:
            cost[nx] = t + nt # nx비용 초기화
            heapq.heappush(hq, [cost[nx], nx])


# star -> 집의 최소경로
hq = []
costt = [float('inf')] * (n + 3)
costt[starV] = 0
heapq.heappush(hq, [0, starV])

while hq:
    t, x = heapq.heappop(hq) # t: 현재까지의 가중치, x는 현재 노드
    if costt[x] != t: continue
    for nx, nt in (adj[x]): # nx는 노드, nt는 가중치
        # 가상의 노드를 지날순 없음
        if nx == macV or nx == starV: continue
        
        if costt[nx] > t + nt:
            costt[nx] = t + nt # nx비용 초기화
            heapq.heappush(hq, [costt[nx], nx])

ans = float('inf')
for i in range(1, n + 1):
    # 정점이 맥도날드나 스타벅스에 위치하면 오답.
    if i in macList: continue
    if i in starList: continue
    if cost[i] <= macinHome and costt[i] <= starinHome: ans = min(ans, cost[i] + costt[i])
if ans == float('inf'): print(-1)
else: print(ans)

---

문제 풀이

 

처음 이 문제를 풀어보려 했을 땐  맥도날드의 수만큼 반복하여 다익스트라를 통해 나온 값중 가장 최솟값을 저장한 배열을 만들고,

스타벅스도 같은 방식으로 최솟값을 저장한 배열을 만들어주어 두 배열의 합 중 스타벅스와 맥도날드가 위치하지 않은 정점을 정답으로 구하려 했다. 시간 초과가 걸릴거라 예상했다. 직접 구하고 보니 역시 시간초과가 나왔고 다른 방법을 생각해 보았다.

 

여러 방법을 찾아본 결과 맥도날드들의 위치를 가중치 0으로 잇는 가상의 정점을 만드는 방법을 찾았다.

이러한 방법으로 맥도날드들과 가상의 맥도날드를 가중치 0으로 이은 간선을 인접리스트에 저장을 한 후 시작 노드를 가상의 맥도날드 지정한다면 다익스트라를 굳이 맥도날드의 수만큼 돌릴 필요가 없어진다. 가상의 노드로 부터 이어진 맥도날드들에 최단거리로 다익스트라에 저장되기 때문에 한번의 다익스트라로 최단거리를 구할 수 있는 것이다.

이 방법으로 맥도날드와, 스타벅스의 최단거리를 구하면 되는데 한가지 반례가 생긴다. 가상의 맥도날드, 스타벅스를 지나가는 경우가 생기는데 이는 원래 없던 길이므로 이 경우는 갈 수 없도록 해주어야 한다.

 

예를 들어 [가상맥 -> a -> c -> 최단노드] 로가는 길보다 [가상맥 -> 가상스타 -> c -> 최단노드] 로 가는길이 최단거리로 나올 수 있지만 이길은 문제에서 구하는 정답이 될 수 없기 때문이다.

 

따라서 다익스트라 부분에서 해당부분을 다음과 같은 조건문으로 반례를 해결해 주었다.

while hq:
    t, x = heapq.heappop(hq) # t: 현재까지의 가중치, x는 현재 노드
    if costt[x] != t: continue
    for nx, nt in (adj[x]): # nx는 노드, nt는 가중치
        # 가상의 노드를 지날순 없음
        if nx == macV or nx == starV: continue
        
        if costt[nx] > t + nt:
            costt[nx] = t + nt # nx비용 초기화
            heapq.heappush(hq, [costt[nx], nx])

 

 

참고자료: https://xyom.github.io/2017/12/26/%E1%84%87%E1%85%A2%E1%86%A8%E1%84%8C%E1%85%AE%E1%86%AB%2013911%20%E1%84%8C%E1%85%B5%E1%86%B8%20%E1%84%80%E1%85%AE%E1%84%92%E1%85%A1%E1%84%80%E1%85%B5/

백준 13911 집 구하기

 

원문: https://ddingmin00.tistory.com/31

[BOJ/python] 13911번 집 구하기