3/23 Coding Test

✅ 문제 풀이 - 그래프 이론

🎈 1753 최단 경로

방향 그래프가 주어지면 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하는 문제.
첫 줄에 정점 수 v, 간선 수 e가 주어지고 모든 정점은 1~v까지 번호가 매겨져 있다. 시작점이 둘째 줄에 주어지고 3번째 줄부터 v+2번째 줄까지 u, v, w가 주어진다.
이때 의미는 u노드에서 v노드로 이동하는데 가중치가 w인 간선을 의미한다.
최종적으로 i번째 줄에 i번 정점으로 이동하는 최단 경로 값을 출력하는 문제로, 시작점은 0을 출력하고, 경로가 존재하지 않으면 INF를 출력한다.

import sys
import heapq
INF = sys.maxsize
input = sys.stdin.readline
# 노드 수, 간선 수, 시작 정점, 그래프 생성
V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V+1)]
# 주어진 간선 수만큼 그래프에 도착지, 가중치 입력
for _ in range(E):
    start, end, cost = map(int, input().split())
    graph[start].append([end, cost])

def dijstra(start):
	# 노드 간 거리 저장 및 힙 생성, 시작지점 힙에 삽입 및 시작점 0으로 초기화
    distance = [INF] * (V+1)
    heap = []
    heapq.heappush(heap, [start, 0])
    distance[start] = 0
    # 힙이 빌때까지 반복
    while heap:
    	# 현 위치 힙에서 빼주고
        now_node, now_cost = heapq.heappop(heap)
        # 현위치와 연결된 다음 위치, 가중치에 한해
        for next_node, next_cost in graph[now_node]:
            # 다음 위치 방문 시 가중치 합 처리
            next_cost = next_cost + now_cost
            # distance내 값이 현재 INF이므로 최소로 갱신 해주기
            if next_cost < distance[next_node]:
                distance[next_node] = next_cost
                heapq.heappush(heap, [next_node, next_cost])
    return distance
    
answer = dijstra(K)
for i in range(1, len(answer)):
    if i == K:
        print(0)
    elif answer[i] == INF:
        print("INF")
    else:
        print(answer[i])

< 풀이 과정 >
다익스트라와 우선순위 큐를 이용하여 구현해 해결한 문제

• 노드, 간선 수 입력받고 시작정점 k 입력받은 후 graph 크기를 (노드 수 + 1)만큼 미리 생성한다. 그 이후 주어진 간선의 도착지와 가중치를 그래프 시작점에 저장한다.
• dijkstra 함수를 구현하여 start 지점의 distance를 0으로 놓고 heapq로 해당 노드의 최솟값을 갱신해준다. 이후 distance를 리턴해준다.
• 이후 answer를 for문으로 탐색하며 시작지점이면 0을, 방문한 적 없는 노드면 INF를 나머지의 경우는 최솟값으로 갱신된 distance를 출력한다.

🎈 11725 트리의 부모 찾기

루트 없는 트리가 주어지고 트리의 루트를 1이라고 할 때, 각 노드의 부모를 찾는 문제
첫 줄에는 노드 개수가 주어지고 둘째 줄부터 n-1줄까지 트리 상 연결된 두 노드가 주어진다.

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (n+1)
def bfs():
    queue = deque()
    queue.append(1)
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if answer[i] == 0:
                answer[i] = x
                queue.append(i)
bfs()
for i in answer[2:]:
    print(i)

< 풀이 과정 >
bfs로 트리를 구현하여 부모 노드를 찾도록 구현한 문제
우선 노드 수 n과 n+1만큼의 graph를 만들어준 이후 a, b를 입력받아 양방향 그래프로 구현해준다.
bfs 함수를 통해 deque를 만들어 우선 부모 노드인 1을 넣어주고 1에서 빼가면서 아래로 내려갈 때 방문한 적이 없다면 꺼낸 노드 숫자를 answer에 저장하는 방식으로 진행
최종적으로 2번노드부터 순서대로 부모 노드 번호를 출력하는 것을 반영하기 위해 for문으로 answer[2:]를 적용하여 출력하였다.