2025.03.29
TIL(TODAY I LEARN)
-
WEEK03 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 -
어제 배운 개념들을 통해 알고리즘 문제들을 풀어보자.
11724 - 연결 요소의 개수 - 실버2
문제 링크 - https://www.acmicpc.net/problem/11724
내 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
V,E = map(int,input().split())
graph = [[] for _ in range(V+1)]
for _ in range(E):
u,v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * (V+1)
def dfs(x):
visited[x] = True
for i in graph[x]:
if visited[i] == False:
dfs(i)
cnt = 0
i = 1
for i in range(1,V+1):
if visited[i] == False:
dfs(i)
cnt += 1
print(cnt)다른 코드(유니온 파인드 사용)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
# 각 노드의 대표(parent)를 저장하는 딕셔너리
parent = {i: i for i in range(1, n + 1)}
# 두 노드의 대표를 찾는 함수 (find)
def find(x):
while parent[x] != x:
x = parent[x]
return x
# m개의 간선 정보 입력
for _ in range(m):
u, v = map(int, input().split())
u_root = find(u)
v_root = find(v)
# 더 작은 번호를 대표로 삼음 (작은 번호가 루트가 되도록)
min_root = min(u_root, v_root)
max_root = max(u_root, v_root)
parent[max_root] = min_root
# 최종적으로 각 노드의 대표를 찾아서 집합 구성
components = set()
for i in range(1, n + 1):
components.add(find(i))
# 연결 요소의 개수 출력
print(len(components))
문제 분류
- 유니온 파인드 방법이 익숙해 지지 않는다.
그래서 최소 스패닝 트리 구할때도 프림 알고리즘을 썼던 것 같다.
유니온 파인드랑 친해지자.
1707 - 이분 그래프 - 골드4
문제 링크 - https://www.acmicpc.net/problem/1707
내 코드
import sys
sys.setrecursionlimit(10**6)
from collections import deque
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
check = True
V,E = map(int,input().split())
graph = [[] for _ in range(V+1)]
for _ in range(E):
u,v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
visited = [-1] * (V+1)
def dfs(start,color):
global check
visited[start] = color
for i in graph[start]:
if visited[start] == visited[i]:
check = False
return
if visited[i] == -1:
dfs(i,(color + 1)%2)
for i in range(1,V+1): #모든 정점에서 dfs 해서 분리된 그래프에서도 돌아가게
if visited[i] == -1:
dfs(i,0)
if check:
print("YES")
else:
print('NO')
문제 분류
-
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.
-
새로운 개념이 나왔다. 그래프의 세계는 끝이 없다....
18352 - 특정 거리의 도시 찾기 - 실버2
문제 링크 - https://www.acmicpc.net/problem/18352
내 코드
import sys
from collections import deque
input = sys.stdin.readline
N,M,K,X = map(int,input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
u,v = map(int,input().split())
graph[u].append(v)
visited = [-1] * (N+1)
def bfs(start):
visited[start] = 0
q = deque([start])
while q:
x = q.popleft()
for i in graph[x]:
if visited[i] == -1:
q.append(i)
visited[i] = visited[x] + 1
bfs(X)
cnt = 0
for i,k in enumerate(visited):
if k == K:
cnt +=1
print(i)
if cnt == 0:
print(-1)문제 분류
그래프가 확실히 알아야 하는 개념도 많고 되게 깊은 분야인 것 같다.
해도해도 끝이 없다. 화이팅
^_^