WEEK 03 알고리즘 TIL(3월31일 월요일)

오늘은 최소 신장 트리에 대해 완벽히 이해하고 코드 구성에 대해 공부했다. 해당 관련 개념은 다른 포스트에 따로 올리겠다.

3번 1197 최소 스패닝 트리

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

최소 스패닝 트리를 풀기 위해서는 크루스칼과 프림 알고리즘이 있다. 그러나 크루스칼은 유니온 파인드라는 이론을 알아야하기 때문에 프림 알고리즘으로 구현해봤다. 프림 알고리즘은 임의의 노드에서 시작해서 다음 노드중 가장 적은 비용의 간선을 찾으면서 확장합니다.

# 다음은 V 정점에 해당되는 E개의 간선 정보를 받아 합해서 최소 신장 트리의 가중치 합을 출력하는 원리의 코드이다.
import sys
import heapq

def prim(V, edges):    # 입력된 정점 개수 V와 간선 값을 받는다.
    # 그래프를 인접 리스트 형태로 저장 (1번 노드부터 V번 노드까지 빈 리스트 초기화)
    graph = {i: [] for i in range(1, V + 1)}   
    
    # 간선 정보를 인접 리스트에 추가 u와 v는 정점 (양방향 그래프이므로)
    for u, v, w in edges:
        graph[u].append((v, w))  # u에서 v로 가는 간선 w
        graph[v].append((u, w))  # v에서 u로 가는 간선 w
    
    mst_weight = 0   # 최소 신장 트리의 가중치 합을 저장할 변수
    visited = [False] * (V + 1)   # 방문 여부 체크 리스트 (1-based index 사용, 1번부터 인덱스 시작)
    priority_queue = [(0, 1)]  # (가중치, 시작 노드) 형태의 우선순위 큐 (초기값: 0번 가중치로 1번 노드 시작)
    
    while priority_queue:
        weight, u = heapq.heappop(priority_queue)  # 가중치가 가장 작은 간선 선택
        if not visited[u]:   # 해당 노드가 방문되지 않았다면
            visited[u] = True  # 방문 완료 처리
            mst_weight += weight   # 최소 신장 트리 합에 추가
            
             # 현재 노드(u)와 연결된 간선들을 확인하여 우선순위 큐에 추가
            for v, w in graph[u]:
                if not visited[v]:    # 아직 방문하지 않은 노드라면
                    heapq.heappush(priority_queue, (w, v))   # 우선순위 큐에 추가
    
    return mst_weight   # 최종 최소 신장 트리 합 리턴

# 입력 받기
V, E = map(int, sys.stdin.readline().split())
edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(E)] # 간선의 개수 E만큼 값을 받는다.

# 결과 출력
print(prim(V, edges))

여러 최소신장 트리 구하는 코드중에 위의 코드가 간결하고 이해하기 용이한 것 같다. 해당 코드들을 잘 외워보겠다.

4번 1260 DFS와 BFS

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

기본적으로 그래프를 구현하고 방문했는지 알기 위한 visited가 있어야한다. 2차원 배열을 만들어서 모두 False처리하고 입력값에 따라 True로 받는다 dfs는 검색지점을 계속 옮기며 재귀함수로 실행하며 깊이 우선 탐색을 하고 bfs는 첫 정점에서 갈 수 있는 곳을 큐에 저장하여 큐가 모두 소진할 때까지 진행한다.

import sys

def dfs(idx) :
    global visited   # 방문기록을 지역변수로 불러옴
    visited[idx] = True   # 정점의 방문기록 True
    print(idx, end = ' ')  # 정점을 출력
    for next in range(1, N+1) :   # 인덱스 1부터 끝까지 순회하며 확인 
        if not visited[next] and graph[idx][next]:  # 방문하지 않았고 간선이 존재하는 정점이라면
            dfs(next)   # dfs에 재귀적으로 입력

def bfs():
    global q, visited  # 방문기록, 큐를 지역변수로 불러옴
    while q:   # 큐가 빌때까지 실행
        cur = q.pop(0)  # 현재 큐 중에 맨 앞 큐를 pop한 것을 cur에 저장
        visited[cur] = True   # 방문을 True로 바꿈
        print(cur, end = ' ')  # cur을 차례대로 출력
        for next in range(1, N + 1) :  # 인덱스 1부터 끝까지 순회하며 확인
            if not visited[next] and graph[cur][next]:  # 방문하지 않았고 간선이 존재하는 정점이라면
                visited[next] = True   # 다음 방문할 곳을 방문했다고 표시
                q.append(next)   # 다음 방문지를 큐에 저장

# 0. 입력 및 초기화
input = sys.stdin.readline
N, M, V = map(int, input().split())  # 입력값 받음
# N은 정점의 총 개수, M은 간선의 총 개수, V는 첫 정점

graph = [[False] * (N + 1) for _ in range(N + 1)]  # 그래프를 N*N만큼 2차원 배열로 표현(초기는 모두 Flase)
visited = [False] * (N + 1)   # 방문자도 N만큼 Flase로 지정

# 1. graph 정보 입력
for _ in range(M) :
    a, b = map(int, input().split())
    graph[a][b] = True  # 입력된 좌표는 갈 수 있음을 표시
    graph[b][a] = True  # 입력된 좌표는 갈 수 있음을 표시

# 2. dfs 
dfs(V)
print()

# 3. bfs
visited = [False] * (N + 1)  # 방문자도 N만큼 Flase로 지정
q = [V]  # Q에 초깃값 입력
bfs()

이론은 알기에 수월했는데 코드로 구현은 이해할 듯하는데 코드로 구현하긴 어려운 것 같다. 생각보다 코드가 간단했지만, 디테일한 부분이 있어서 이해하기 좀 어려웠다.


18:00 ~ 19:00
식사를 하고 왔다. 내일 퀴즈에서 다익스트라 정렬 알고리즘이 나온다고 해서 개념 먼저 공부하겠다. 코드까지…
이후에 이번주 컴퓨터 시스템에 대해 정리를 팀원분과 함께 했다. 해당내용도 따로 포스팅하겠다.