크루스칼 알고리즘
최소의 비용으로 모든 노드가 연결된 최소 스패닝 트리를 만들 수 있는 알고리즘이다.
union-find 방법(서로소 집합)을 통해 사이클을 판별하는 방법은 무방향 그래프에서만 가능하다.
- 그래프에 대한 간선 정보만 따로 빼내서 오름차순으로 정렬한다.
간선을 하나씩 확인하며 간선이 사이클을 발생시키는지 확인
(사이클 발생 확인 방법 : 연결된 루트 노드가 같은지)
2-1. 사이클X, 최소 스패닝 트리에 포함
(노드와 노드의 루트 노드를 연결)
2-2. 사이클O, 최소 스패닝 트리에 포함X- 모든 간선에 대해서 2번 과정 반복
방향 그래프에서 사이클 찾기
방향 그래프에서 사이클이란 특정 정점에서 시작하여 어떤 경로를 지나 다시 그 정점으로 돌아오는 경로를 의미한다. 따라서 DFS를 이용해 그래프를 탐색하며, 시작점과 방문점이 같은 경우 사이클이 존재한다고 판단할 수 있다. 참고한 블로그
코드 : 시간복잡도 O(V(V+E)
from collections import defaultdict
def solution1():
N = 7
# 4,6,7 노드간 사이클 존재
edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (6, 4), (4, 7), (7, 6)]
graph = defaultdict(list)
for edge in edges:
s, e = edge
# 그래프 연결
graph[s].append(e)
visit = [0] * (N + 1)
# 시간복잡도 DFS O(V+E),
# 모든 정점에 하므로 O(v(V+E))
def dfs(start, here):
# 재귀 함수 종료 조건
# 이미 방문했고
if visit[here]:
# 시작 정점과 현재 방문 정점이 같다면 싸이클
if start == here:
return False
# 같지 않다면 싸이클X 노드에서 온 것임
return True
# 방문 처리
visit[here] = True
for node in graph[here]:
# 시작 정점을 그대로 둔 채로 DFS로 노드 계속 탐색
if dfs(start, node):
# DFS가 true를 반환하는 경우 사이클 존재
return True
return False
# 시간복잡도 O(V+E)로 해결하기
# DFS를 수행하다가 재귀 탐색이 종료되지 않았는데 다시 방문하게 되면 사이클 O
# 사이클이 존재하는 노드와 연결된 노드로부터 사이클 존재여부 바로 확인O
def dfs2(here):
if visit[here]:
# DFS가 아직 안 끝났는데 사이클
if visit[here] == -1:
return True
return False
# DFS 아직 안 끝남
visit[here] = -1
for node in graph[here]:
if dfs(node):
return True
# DFS가 끝났으므로 1로 설정
visit[here] = 1
return True
for i in range(1, N + 1):
# 사이클이 하나라도 존재한다면 사이클이 있는 그래프
if dfs(i, i):
return True
return False
print(solution1())코드 : 시간복잡도 O(V+E)
from collections import defaultdict
def solution2():
N = 7
# 4,6,7 노드간 사이클 존재
edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (6, 4), (4, 7), (7, 6)]
graph = defaultdict(list)
for edge in edges:
s, e = edge
# 그래프 연결
graph[s].append(e)
visit = [0] * (N + 1)
# 시간복잡도 O(V+E)로 해결하기
# DFS를 수행하다가 재귀 탐색이 종료되지 않았는데 다시 방문하게 되면 사이클 O
# 사이클이 존재하는 노드와 연결된 노드로부터 사이클 존재여부 바로 확인O
def dfs2(here):
if visit[here]:
# DFS가 아직 안 끝났는데 사이클
if visit[here] == -1:
return True
return False
# DFS 아직 안 끝남
visit[here] = -1
for node in graph[here]:
if dfs2(node):
return True
# DFS가 끝났으므로 1로 설정
visit[here] = 1
return True
return dfs2(1)
print(solution2())그리디 (크루스칼 알고리즘)
골드4. 백준 1197 최소 스패닝 트리
풀이
크루스칼 알고리즘 (그리디)
1. 간선을 오름차순으로 정렬
2. 간선을 하나씩 확인하며 간선이 사이클을 발생시키는지 확인
(사이클 발생 확인 방법 : 연결된 루트 노드가 같은지)
2-1. 사이클X, 최소 스패닝 트리에 포함
(노드와 노드의 루트 노드를 연결)
2-2. 사이클O, 최소 스패닝 트리에 포함X
3. 모든 간선에 대해서 2번 과정 반복
크루스칼 알고리즘을 연습하기 좋은 문제.
코드
from sys import stdin
input = stdin.readline
V, E = map(int, input().split(" "))
dist = []
for _ in range(E):
a, b, c = map(int, input().split(" "))
dist.append([a, b, c])
# 간선을 오름차순으로 정렬
dist.sort(key=lambda x: (x[2]))
# 부모 테이블
parent = [i for i in range(V + 1)]
def find_parent(parent, n):
if parent[n] != n:
parent[n] = find_parent(parent, parent[n])
return parent[n]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
answer = 0
for a, b, edge in dist:
# 사이클 존재 X
if find_parent(parent, a) != find_parent(parent, b):
# 연결하고 최소 스패닝 트리에 포함 (가중치만 출력하면 되므로 합계)
union_parent(parent, a, b)
answer += edge
print(answer)골드4. 백준 1922 네트워크 연결
풀이
크루스칼 알고리즘 연습하기 좋은 다른 문제! 응용 없이 완전 기본 문제다. 크루스칼 알고리즘을 써야해서 골드에 난이도가 책정된듯?
코드
from sys import stdin
input = stdin.readline
N = int(input()) # 정점
M = int(input()) # 간선
dist = []
for _ in range(M):
a, b, c = map(int, input().split(" "))
dist.append((a, b, c)) # a-b : 비용 c
# 간선비용 기준 정렬
dist.sort(key=lambda x: (x[2]))
parent = [i for i in range(N + 1)]
# union-find
def find_parent(parent, n):
if parent[n] != n:
parent[n] = find_parent(parent, parent[n])
return parent[n]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
answer = 0
for a, b, cost in dist:
if find_parent(parent, a) != find_parent(parent, b):
# 사이클 X => 연결 후 최소 스패닝 트리에 포함
union_parent(parent, a, b)
answer += cost
print(answer)✨골드1. 백준 17472 다리 만들기 2
풀이
✨ 달아놓은 이유는... 잘풀어서 뿌듯해서....^^
구현문제처럼 차근차근 문제를 따라가면 되는 문제다.
그래프에 땅(1), 바다(0) 좌표가 주어진다. 상하좌우로 인접한 땅을 하나의 섬으로 친다. 각 섬에서 상하좌우 중 한 방향으로만 직진하여 바다 위에 다른 섬으로 가는 다리를 만들 수 있는데 다리의 최소 길이는 2이다.
무방향 그래프니 크루스칼 알고리즘을 사용하여 다리의 모든 경우의 수를 구하여 짧은 것만 연결해주면 된다!
섬의 좌표를 각 섬 별로 저장했으며 (섬에 따라 인덱스가 다르다) 상하좌우로 쭉 직진하며 만약 다른 섬이 등장하는 경우(섬인데 인덱스가 본인과 다른 경우) 다리의 길이가 1보다 크면 저장해주었다.
(시작 정점, 끝나는 정점이 바뀐 경우를 또 저장할 필요가 없어서 빼줬는데 어차피 서로소 알고리즘을 사용할 것이니 이 부분은 뺴줘도 될 것 같다)
주의할 점은 마지막에 모든 섬이 연결되었는지 체크해줘야 한다는 것이다. 따라서 생성된 다리 개수가 섬의 개수-1 인지 체크해줘야 한다.
골드1문제를 1시간 언저리로 안정적으로 풀어서 기쁘다.
코드
from sys import stdin
from collections import deque
input = stdin.readline
# N : Row, M : Col
N, M = map(int, input().split(" "))
graph = [list(map(int, input().split(" "))) for _ in range(N)]
islands = []
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
def find_island(sr, sc):
temp = [(sr, sc)]
q = deque([(sr, sc)])
graph[sr][sc] = 2 # 방문처리
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < M:
if graph[nr][nc] == 1:
# 방문처리, 큐에 넣기, 섬 좌표값 저장
graph[nr][nc] = 2
q.append((nr, nc))
temp.append((nr, nc))
islands.append(temp)
for r in range(N):
for c in range(M):
if graph[r][c] == 1:
find_island(r, c)
def find_island_idx(r, c):
for i in range(len(islands)):
if (r, c) in islands[i]:
return i
dist = []
# idx : 섬 번호
for idx in range(len(islands)):
for r, c in islands[idx]:
# 섬 좌표 별로 4방향으로 쭉 직진하면서 다른 섬이 있는지 체크
for i in range(4):
count = 0
nr = r + dr[i]
nc = c + dc[i]
while 0 <= nr < N and 0 <= nc < M:
# 바다
if graph[nr][nc] == 0:
nr += dr[i]
nc += dc[i]
count += 1
# 섬
else:
other_island = find_island_idx(nr, nc)
if idx != other_island and count != 1:
if (other_island, idx, count) not in dist:
dist.append((idx, other_island, count))
break
parent = [i for i in range(len(islands))]
def find_parent(parent, n):
if parent[n] != n:
parent[n] = find_parent(parent, parent[n])
return parent[n]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
bridge = 0
answer = 0
dist.sort(key=lambda x: (x[2]))
for a, b, cost in dist:
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
bridge += 1
answer += cost
# 모든 섬이 연결되었는지 체크
if bridge != len(islands) - 1:
print(-1)
else:
print(answer)
최단거리
다익스트라
- 출발 노드를 설정
- 최단 거리 테이블을 초기화 (무한의 값 int(1e9사용)
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (그리디)
: 가장 짧은 노드를 빠르게 찾을 수 있도록 힙 (heapq) 자료구조 사용 - 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 3,4번 과정 반복
골드4. 백준 1504 특정한 최단 경로
풀이
40분정도 걸려서 풀었다. 아이디어를 고민하는데 20분 구현하는데 20분정도 걸린 것 같다.
문제를 살펴보면 일반적인 최단 경로 문제와 비슷하나, 특이점이 하나 있다. 특정한 두 정점(v1, v2)을 반드시 지나가야 한다는 것이다.
따라서 고려해야 하는 경우는 2가지다.
1->v1->v2->N1->v2->v1->N
따라서 각각 1, v1, v2에서 시작하는 최단 거리 테이블이 총 3개 필요하다.
더해서 최솟값을 출력해주면 된다. 만약 불가능한 경우 -1을 출력
코드
from sys import stdin
import heapq
input = stdin.readline
N, E = map(int, input().split(" "))
# 노드
graph = [[] for _ in range(N + 1)]
for _ in range(E):
a, b, c = map(int, input().split(" "))
graph[a].append((b, c))
graph[b].append((a, c))
v1, v2 = map(int, input().split(" "))
def dijkstr(start, distance):
q = []
distance[start] = 0
heapq.heappush(q, (0, start)) # 비용, 노드
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
next_node, next_node_cost = i
cost = dist + next_node_cost
if distance[next_node] > cost:
distance[next_node] = cost
heapq.heappush(q, (cost, next_node))
# 1번 정점에서 시작하는 거리 그래프
distance1 = [int(1e9) for _ in range(N + 1)]
dijkstr(1, distance1)
# v1번 정점에서 시작하는 거리 그래프
distanceV1 = [int(1e9) for _ in range(N + 1)]
dijkstr(v1, distanceV1)
# v2번 정점에서 시작하는 거리 그래프
distanceV2 = [int(1e9) for _ in range(N + 1)]
dijkstr(v2, distanceV2)
answer = 0
# 1->v1->v2->N
if (
distance1[v1] != int(1e9)
and distanceV1[v2] != int(1e9)
and distanceV2[N] != int(1e9)
):
answer = distance1[v1] + distanceV1[v2] + distanceV2[N]
# 1->v2->v1->N
if (
distance1[v2] != int(1e9)
and distanceV2[v1] != int(1e9)
and distanceV1[N] != int(1e9)
):
answer = min(answer, distance1[v2] + distanceV2[v1] + distanceV1[N])
if answer == 0:
print(-1)
else:
print(answer)골드1. 백준 16118 달빛 여우
풀이
경우를 나눠서 최단경로를 체크해야한단 점에서 어제 푼 골드3. 백준 2206 벽 부수고 이동하기 문제와 비슷하다.
비슷한데 왜 캐치를 못하고... 예제를 이해 못했는지 조금 슬프다!!
여우는 일반적인 다익스트라 방식으로 풀면 된다.
늑대가 문제인데, 늑대는 빠르게 / 느리게를 번갈아가며 이동한다. 따라서 소숫점이 나오지 않도록 간선의 가중치를 다 x2해주고 시작했다.
핵심 포인트는 늑대가 특정 좌표까지 빠르게 도착했는지 / 느리게 도착했는지를 나눠서 봐야 한다.
따라서 빠르게 도착했는지의 여부를 arrive_fast 변수로 힙에 같이 넣어주었고, 빠르게 도착했을 때의 거리값은 distance[node][0]에 느리게 도착했을 때의 거리값은 distance[node][1]에 넣어주었다.
엄청나게 헷갈린다!!!!
비교해야되는 데이터가 헷갈려서 예시를 자세히 적어둔다.
이전 데이터와 비교해서 업데이트해줄 때,
빠르게 도착한 경우 이제 느리게 출발해야된다. 따라서 거리값은 x2해준다. 그리고 비교해야 될 데이터는 현재 선택한 경로cost와 다음 도착할 거리값(느리게 출발했으니 -> 다음 노드 기준 느리게 도착했을 때)을 갱신해줘야 하므로 distance[next_node][1] 를 비교한다.
코드
from sys import stdin
import heapq
input = stdin.readline
# N : 정점, M : 간선
N, M = map(int, input().split(" "))
graph = [[] for _ in range(N + 1)]
for _ in range(M):
a, b, d = map(int, input().split(" "))
graph[a].append((b, d * 2))
graph[b].append((a, d * 2))
distance_fox = [int(1e9) for _ in range(N + 1)]
distance_wolf = [[int(1e9)] * 2 for _ in range(N + 1)]
def dijkstra_fox(start):
q = []
heapq.heappush(q, (0, start))
distance_fox[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance_fox[now] < dist:
continue
for i in graph[now]:
next_node, next_node_cost = i
cost = dist + next_node_cost
if distance_fox[next_node] > cost:
distance_fox[next_node] = cost
heapq.heappush(q, (cost, next_node))
def dijkstra_wolf(start):
q = []
# 빨리 도착했는지(True): distance[0], 느리게 도착했는지(False) : distance[1]
heapq.heappush(q, (0, start, False))
distance_wolf[start][1] = 0
while q:
dist, now, arrive_fast = heapq.heappop(q)
if arrive_fast and distance_wolf[now][0] < dist:
continue
elif not arrive_fast and distance_wolf[now][1] < dist:
continue
for i in graph[now]:
next_node, next_node_cost = i
# 빠르게 도착했으니, 느리게 출발
if arrive_fast:
next_node_cost *= 2
cost = dist + next_node_cost
if distance_wolf[next_node][1] > cost:
distance_wolf[next_node][1] = cost
heapq.heappush(q, (cost, next_node, False))
else:
next_node_cost //= 2
cost = dist + next_node_cost
if distance_wolf[next_node][0] > cost:
distance_wolf[next_node][0] = cost
heapq.heappush(q, (cost, next_node, True))
dijkstra_fox(1)
dijkstra_wolf(1)
answer = 0
for i in range(2, N + 1):
if distance_fox[i] < min(distance_wolf[i][0], distance_wolf[i][1]):
answer += 1
print(answer)DP
이미 계산된 결과는 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방식
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 사용한다.
동일한 작은 문제를 반복적으로 해결해야 할 때 사용한다.
메모이제이션
DP를 구현하는 방법 중 하나로 한번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 호출하면 메모했던 결과를 그대로 가져옴 (다시 계산X)
- 값을 기록해놓는다는 점에서 캐싱이라고도 함
📌 골드3. 백준 1520 내리막길
DP는 문제 푸는 방법이 보일 때까지 반복 또 반복하자!!!!!!
풀이
DFS, BFS 뭘 해도 시간초과가 안 잡혀서 해설을 찾아봤다. DP를 적용시켜야 하는 문제였다.
이 문제의 경우 시작, 도착점이 아닌 임의의 지점(a,b)에서 도착지점 (m-1, n-1) 까지 가는 경우의 수가 구해지면, 그 이전의 어떤 경로로 (a,b)에 도착하기만 하면 그 때부터의 경우의 수는 다시 구할 필요가 없다. 즉, 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같아진다.
어떻게 메모이제이션을 할까 -> 시작 지점에서 출발해서 DP 테이블이 갱신되지 않은 곳(X)을 만난다면, 해당 지점(X)부터 도착 지점까지 갈 수 있는 경로의 수를 그곳에 업데이트. X지점의 DP 테이블이 이미 갱신되어 있다면 그 곳이 위에서 말한 부분 최적해가 되므로 그 값을 그대로 전체 정답에 더해주면 된다.
코드
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
# M : row, N : col
M, N = map(int, input().split(" "))
graph = [list(map(int, input().split(" "))) for _ in range(M)]
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
dp = [[-1 for _ in range(N)] for _ in range(M)]
# dfs(r, c) -> (r, c)에서 출발하여 (N-1, M-1)까지 가는 경우의 수
def dfs(r, c):
# 재귀함수 종료조건
if r == M - 1 and c == N - 1:
return 1
# 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴받아
# 그 경우는 다시 탐색하지 않음
if dp[r][c] != -1:
return dp[r][c]
dp[r][c] = 0
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < M and 0 <= nc < N:
if graph[nr][nc] < graph[r][c]:
dp[r][c] += dfs(nr, nc)
return dp[r][c]
print(dfs(0, 0))골드4. 백준 16234 인구 이동
풀이
문제에서 나오는 대로 구현하면 되는 문제다. 그래프(BFS) + 구현 느낌?
상하좌우를 살펴보면서 좌표간의 차이가 L 이상 R 이하인 경우 연합 move_pos에 추가하고 방문처리를 해주었다.
한번이라도 인구이동이 발생했으면 is_move_ocurred를 True로 바꿔 다시 전체 BFS를 돌리도록 구현했다.
한번도 인구이동이 발생하지 않을 수 있으므로 인구이동이 발생한 날짜day의 기본값은 0으로 설정했다.
문제 조건 잘 읽고 이해한 뒤 예제 잘 적용시켜보고 구현했더니 30~40분정도 걸려서 기분이 좋았다.
코드
from sys import stdin
from collections import deque
input = stdin.readline
N, L, R = map(int, input().split(" "))
graph = [list(map(int, input().split(" "))) for _ in range(N)]
# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
# 인구이동 발생 여부 return (발생시 True)
def bfs(sr, sc, visit):
global is_move_ocurred
move_pos = [(sr, sc)]
total_ppl = graph[sr][sc]
q = deque([(sr, sc)])
visit[sr][sc] = True
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N and not visit[nr][nc]:
if L <= abs(graph[r][c] - graph[nr][nc]) <= R:
move_pos.append((nr, nc))
total_ppl += graph[nr][nc]
q.append((nr, nc))
visit[nr][nc] = True
if len(move_pos) != 1:
is_move_ocurred = True
num = total_ppl // len(move_pos)
for r, c in move_pos:
graph[r][c] = num
day = 0
is_move_ocurred = False
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
for c in range(N):
if not visit[r][c]:
bfs(r, c, visit)
if is_move_ocurred:
day = 1
while is_move_ocurred:
is_move_ocurred = False
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
for c in range(N):
if not visit[r][c]:
bfs(r, c, visit)
if is_move_ocurred:
day += 1
print(day)