[BOJ] 백준 17396번 백도어 (Python)

 

---

 

☁️ 문제 이해하기

• 문제
  •  입력
    • 첫째줄: 분기점의 수 n, 분기점들을 잇는 길의 수 m
    • 둘째줄: 각 분기점이 적의 시야에 보이는지를 의미하는 n개의 정수 ai
      • ai==0, i번째 분기점이 상대의 시야에 안 보이는 곳
      • ai==1, i번째 분기점이 상대의 시야에 보이는 곳 (지나갈 수 없음)
      • a0=0, an-1=1(마지막 분기점은 상대 시야에 보이면서 유일하게 상대 시야에 보이면서 갈 수 있는 곳)
    • 세번째 ~ m +3번째 줄: start a, end b, t만큼의 시간
    • 양방향, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개
  • 출력
    • 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간 출력하기
    • 만약 상대 넥서스까지 갈 수 없으면 -1 출력
  • 예시 이해하기

5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

 

☁️ 알고리즘

• 다익스트라 사용하기
  
  • 이유
    • 1. 최단 거리를 구해야 함
      • 출발점에서 도착점까지 가장 적은 시간이 걸리는 경로를 구해야 함
    • 2. 가중치가 있는 그래프
      • 각 간선에는 시간 가중치 `t`가 존재

💡`양의 가중치 + 단일 시작점 + 최소 거리`는 무조건 다익스트라를 사용해야 하는 조건임!

 

☁️ 코드 뼈대 세우기

• • 입력 처리
    • 분기점 수 n과 분기점들을 잇는 간선 수 m을 map을 통해 입력받기
    • 적의 시야에 보이는지 여부를 list, map을 사용해 입력받기
    • 감시가 있는 장소는 1, 없는 장소는 0인데 마지막 분기점은 감시가 있어도 지나갈 수 있으니 0으로 설정하기
  • 그래프 생성하기
    • connect[u] = [(비용, v), (비용, w), ...] 형식의 인접 리스트로 생성하기
    • 양방향이니까 양쪽 다 append 해주기
  • 다익스트라 함수
    • 순서
      • 1. 거리 정보 inf로 초기화 (다익스트라의 기본 개념)
      • 2. 우선순위 큐로 최소 거리 노드부터 처리
      • 3. heapq에서 꺼내진 노드와 연결된 모든 노드 확인하기 (for)
      • 4. 조건문 활용해 방문 가능한지 확인 (더 짧은 경로가 있는지? and 감시가 있어 지나갈 수 없는지)
      • 5. 더짧은 경로가 있고 감시자 없다면 거리 갱신 및 heapq에 삽입 
    • 코드
      • start=0, end=n-1
      • dis_list[node]: 시작점에서 해당 노드까지의 최소 거리를 저장
      • heapq(우선순위큐)를 사용해서 자동으로 최소 거리 노드부터 탐색
      • 감시가 있는 곳은 지나갈 수 없으니 arr[next_node]!=1이 아닌 곳만 지나가게 함

 

---

☁️ 코드

import sys
import heapq

# 입력
input = sys.stdin.readline
N,M = map(int, input().split())

arr = list(map(int, input().strip().split()))
arr[-1] = 0		# 마지막 분기점

# 최대값
INF = sys.maxsize

# 그래프 만들기
connect = [[] for _ in range(N)]
for i in range(M):
    a, b, t = map(int, input().split())
    connect[a].append((t, b))
    connect[b].append((t, a))

# 다익스트라
def dijkstra(start, end):
    dis_list = [INF for _ in range(N)]
    dis_list[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))

    while pq:
        dis, node = heapq.heappop(pq)
        if dis > dis_list[node]:		# 이미 더 짧은 경로를 방문한 경우는 skip
            continue
        for next_cost, next_node in connect[node]:	# pop한 노드에서 연결된 노드들 순회하기
            if dis_list[next_node] > dis_list[node]+next_cost and not arr[next_node]:
                dis_list[next_node] = dis_list[node]+next_cost
                heapq.heappush(pq, (dis_list[next_node], next_node))

    return dis_list[end]

num = dijkstra(0, N-1)
if num==INF:
    print(-1)
else:
    print(num)

 

 

☁️ 코드 작성 시 유의할 점

• 1. 마지막 분기점은 0으로 변경해줘야함 -> 지나가야하니까
• 나머지는 일반적인 다익스트라 알고리즘 문제와 비슷