Krafton_jungle 5기 14일차 TIL - 알고리즘 문제풀이

1. 1197 최소 스패닝 트리

import sys
input = sys.stdin.readline

# 크루스칼 알고리즘을 이용한 풀이
v, e = map(int, input().split())
edges = [[int(x) for x in input().split()] for _ in range(e)]
edges.sort(key=lambda x: x[2])  # weight 기준으로 정렬

# 부모를 저장할 테이블
parent = [0] * (v + 1)
for i in range(1, v+1):
    parent[i] = i
result = 0


# 재귀적으로 탐색하며 부모를 return
def find_parent(parent, n):
    if n != parent[n]:
        parent[n] = find_parent(parent, parent[n])
    return parent[n]


# 만약 서로의 부모가 겹치지 않으면 parent에 추가
def union_parent(parent, x, y):
    x = find_parent(parent, x)
    y = find_parent(parent, y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


# 정렬된 배열 기준으로 탐색 시작
for edge in edges:
    x, y, weight = edge
    if find_parent(parent, x) != find_parent(parent, y):
        union_parent(parent, x, y)
        result += weight

print(result)

이론으로만 학습했던 알고리즘을 직접 구현해봤다.
재귀적으로 부모의 노드를 탐색하는 알고리즘을 작성해봤는데 상당히 흥미로움

 

 

2. 1260 DFS와 BFS

import sys
from collections import deque

input = sys.stdin.readline


# 양방향 그래프인걸 깜빡해서 오탑이 떴음
def dfs(start, visited = []):
    visited.append(start)
    for i in graph[start]:
        if i not in visited:
            visited = dfs(i, visited)
    return visited


def bfs(start, visited=[]):
    visited.append(start)
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for i in graph[vertex]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
    return visited


n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for i in range(1, n+1):
    graph[i].sort()

print(*dfs(v))
print(*bfs(v))

기본적인 DFS와 BFS의 탐색 방법을 사용해서 풀이할 수 있는 문제.

재귀에 뇌가 절여져 이제는 뭔가 BFS가 더 이상하다.

 

3. 11724 연결요소의 개수

import sys
sys.setrecursionlimit(1000000)
from collections import deque

input = sys.stdin.readline


def search_connected(graph, res):
    total_visited_vertex[0] = 1
    while sum(total_visited_vertex)-1 != vertex:
        # 방문처리 되지 않은 노드로부터 탐색 시작
        start = total_visited_vertex.index(0)
        dfs(start, set())
        res += 1
    return res


def dfs(start, visited):
    total_visited_vertex[start] = 1
    visited.add(start)
    for i in graph[start]:
        if i not in visited:
            dfs(i, visited)
    return


vertex, edge = map(int, input().split())

graph = deque([] for _ in range(vertex + 1))
total_visited_vertex = [0] * (vertex + 1)
res = 0

# 그래프 생성
for i in range(edge):
    v, e = map(int, input().split())
    graph[v].append(e)
    graph[e].append(v)

print(search_connected(graph, res))

위 DFS의 연장으로 탐색을 진행하며 탐색 노드를 방문처리하고, 모든 노드를 탐색할때까지 반복하는 로직을 작성했다.

나중에 시간나면 BFS로도 탐색해봐야겠다.

 

 

벌써 정글에 들어온지도 2주가 지나간다. 초심을 잃지않고 꾸준히 앞으로 나아가자