크래프톤정글 3주차; TIL 3 - 최소 신장 트리 문제, DFS와 BFS, 연결 요소의 개수 문제

2022-11-13

백준 파이썬 1197번 최소 스패닝 트리

출처:

무엇?

최소 신장 트리 (minimum spanning tree)를 구현하는 문제

왜?

일반 리스트를 사용해서 여러번 도전해봤는데 시간 초과.
처음에 엣지들이 양방향이라는 조건도 놓치기 쉬웠다.

어떻게?

▽ 솔루션을 참고하여 주석을 달아 본 정답 코드

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())  # 노드 개수, 엣지 개수
covered = [0] * (V+1)                          # 방문한 노드들 리스트
edges = [[] for _ in range(V+1)]               # 엣지를 담을 리스트
sum_min_w = 0                                  # 최소 가중치의 합

for e in range(E):
    src, dst, weight = map(int, sys.stdin.readline().split())   # 소스노드, 목적지노드, 가중치
    edges[src].append((weight, dst))    # 양방향이기 때문에 둘 다 추가
    edges[dst].append((weight, src))    # 가중치로 최소 힙을 만들어야하므로 가중치를 0 인덱스에 삽입

min_heap = [(0, 1)]      # (가중치, 목적지노드) 튜플을 담을 우선순위 큐(최소힙)
while min_heap:
    node = heapq.heappop(min_heap)    # min_heap의 최소값을 pop
    if not covered[node[1]]:     # 목적지 노드를 방문한 적 없다면
        covered[node[1]] = 1     # 방문한 노드에 해당 목적지 노드를 체크
        sum_min_w += node[0]     # 가중치 합에 가중치를 추가
        for n in edges[node[1]]: # 목적지 노드를 소스 노드로 삼는 모든 (가중치, 목적지노드)를 최소 힙에 추가
            heapq.heappush(min_heap, n)  

print(sum_min_w)

▽ 내 답 (시간초과)

• 정답과 다른 점
  1. 최소 힙 대신에 일반 리스트 사용
  2. 힙을 사용하지 않았기 때문에, 노드를 모두 커버했는지 확인하기 위해 집합을 사용함
  3. 엣지를 추가할 때 (dst, weight) 순으로 추가 → 정답 코드에서는 (weight, dst) 순

import sys

V, E = map(int, sys.stdin.readline().split())
edges = [[] for _ in range(V+1)]
for _ in range(E):
    src, dst, w = map(int, sys.stdin.readline().split())
    edges[src].append((dst, w))  
    edges[dst].append((src, w))  

covered = [1] + [[] for _ in range(V-1)]
chk = set()
total = 0

while len(chk) != V-1:
    tmp = 2147483648
    for i, v in enumerate(edges):      
        if (i > 0) and (v != []) and (covered[i-1] != []): # 해당 노드가 커버되어있고, 그 노드에서 다른 노드로 가는 엣지들이 존재할 때
            for j in v:  
                if (covered[j[0]-1] == []) and (tmp > j[1]): # 목적지 노드가 커버되지 않았고, 가중치를 비교하여 더 작을 때
                    tmp = j[1]
                    min_edge = j  # 최소가중치를 가진 엣지의 (dst, 가중치) 튜플
    total += min_edge[1]
    dst = min_edge[0]
    covered[dst-1] = dst
    chk.add(dst)

print(total)

'''
bridges = 커버한 노드에서 안 커버한 노드로 가는 엣지들
모든 노드를 다 커버할 때까지 반복
    브릿지 중 최소 가중치를 가진 엣지 e를 찾음
    e의 목적지를 커버한 노드에 추가
    e를 선택한 엣지 집합에 추가
return 선택된 엣지 집합 E, 커버한 노드 U

엣지 집합 E에 대해서
    가중치를 모두 더함
return 가중치의 합
'''

백준 1260번 DFS와 BFS 파이썬

출처: https://www.edwith.org/cs113/lecture/540289/?isDesc=false
https://www.edwith.org/cs113/lecture/540288/?isDesc=false
https://www.acmicpc.net/problem/1260

무엇?

깊이 우선 탐색 알고리즘(BFS)와 너비 우선 탐색(DFS)의 기초적인 개념과 구현에 관한 문제

왜?

그래프 탐색 문제의 기초

어떻게?

▽ 위의 강의를 보고 작성해본 정답 코드 + 미래의 나를 위한 주석
딕셔너리와 파이썬 리스트를 이용

# 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000),
# 간선의 개수 M(1 ≤ M ≤ 10,000),
# 탐색을 시작할 정점의 번호 V

import sys

N, M, V = map(int, sys.stdin.readline().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    src, dst = map(int, sys.stdin.readline().split())
    edges[src].append(dst)  
    edges[dst].append(src)  # 양방향이기에 이 라인 없이 윗 라인만 있으면 오답

for i in edges:    # 숫자가 적은 노드부터 방문해야해서 오름차순 정렬함
    if i != []:
        i.sort()

def bfs(s, edges):
    level = {s: 0}      # 단계(level)은 몇 스텝만에 시작노드에서 해당 노드로 갈 수 있는지를 의미
    parent = {s: None}  # 특정 노드의 부모 노드(전 단계에 있던 노드)를 가리킴
    i = 1               # 단계를 나타낼 i (다음 단계를 탐색할 때마다 +1)
    frontier = [s]      # frontier는 각 레벨에서 탐색하게 될 노드(단계마다 바뀜)
    print(s, end=' ')
    while frontier:     # 탐색할 노드가 존재하지 않을 때까지
        nexts = []      # 다음 단계에서 탐색할 노드를 담을 리스트
        for u in frontier:          # frontier에 있는 시작노드 s에 대해
            for v in edges[u]:      # 그 시작노드가 가진 엣지들의 목적지 노드에 대해
                if v not in level:  # 목적지 노드가 level에 없다면
                    level[v] = i    # v의 레벨은 i단계
                    parent[v] = u   # v의 부모 노드는 u
                    print(v, end=' ')
                    nexts.append(v) # 탐색할 다음 노드에 v를 추가
        frontier = nexts    # 추가 된 다음 노드들을 frontier에 올림
        i += 1

parent = {V: None}          # 부모 노드를 지정해줌으로써 이미 방문했는지 아닌지 판별
def dfs_visit(s, edges):
    global parent
    print(s, end=' ')
    for v in edges[s]:      # 시작 노드의 목적지 노드들에 대해서
        if v not in parent: # 목적지 노드의 부모노드가 지정되지 않았다면(이전에 방문 안 했으면)
            parent[v] = s   # 시작 노드를 해당 노드의 부모노드로 지정
            dfs_visit(v, edges) # 해당 목적지 노드를 대상으로 재귀

dfs_visit(V, edges)
print('')
bfs(V, edges)

백준 11724번 연결요소의 개수

출처: https://www.acmicpc.net/problem/11724

무엇?

너비 우선 탐색(DFS)의 기초적인 개념과 구현에 관한 문제

왜?

백준 1260번 문제
위에서 풀었던 문제는 깊이 우선 탐색의 dfs-visit 함수만 사용하면 되었다.
이 문제에서는 연결 요소(이 포스팅에서 그래프의 ‘component’ 개념 확인 ☞ 컴퓨터 과학, 자료구조, 알고리즘 with C언어)의 개수를 파악하는 문제인데,
이를 위해서는 dfs-visit을 시작할 시작 노드를 바꿔줄, dfs-visit의 상위 알고리즘인 dfs 함수가 필요함.
따라서 정리!!!

어떻게?

import sys
sys.setrecursionlimit(10**9)  # dfs는 재귀를 이용하므로 재귀 에러가 종종 나니 재귀 상한을 늘려주기

N, M = map(int, sys.stdin.readline().strip().split())
edges = [[] for _ in range(N+1)]

for _ in range(M):
    src, dst = map(int, sys.stdin.readline().strip().split())
    edges[src].append(dst)  # 간선을 양방향으로 넣어주어야 정확함!
    edges[dst].append(src)  

count = 0
parent = {}

def dfs_visit(s, edges):
    for v in edges[s]:
        if (v not in parent):    
            parent[v] = s
            dfs_visit(v, edges)

# dfs 함수는 단절된 그래프, 강하게 연결된 그래프가 아닌 경우에 시작 노드를 바꿔 모든 그래프를 탐색하기 위함
def dfs(N, edges):
    global count
    for s in range(1,N+1):  # 모든 노드들에 대해
        if s not in parent: # 이미 방문된 노드가 아니라면
            parent[s] = None # '부모 없음'을 뜻하는 None; dfs_visit을 시작할 노드이기 때문
            count += 1
            dfs_visit(s, edges)

dfs(N, edges)
print(count)