2025.04.02
TIL(TODAY I LEARN)
-
WEEK03 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 -
시험 전 3주차의 마지막 날이다.
- 어제 못풀었던 알고리즘 문제를 풀었다.
21606 - 아침 산책 - 골드3
문제 링크 - https://www.acmicpc.net/problem/21606
내 코드(200점 만점!)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input().strip())
A = [0]
A = A + list(map(int,input().strip()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
u,v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False for _ in range(n+1)]
total_cnt = 0
# 흰색 노드 체크
def dfs(i): # cnt == 흰색 주변 검은색 개수
visited[i] = True
black_cnt = 0
for x in graph[i]:
if visited[x] == False:
if A[x] == 1:
black_cnt += 1
else:
black_cnt += dfs(x)
return black_cnt
for i in range(1,n+1):
if not visited[i] and A[i] == 0:
x = dfs(i)
#흰색 주변 한개 있어도 x-1 에서 0이 되어서 total_cnt는 영향을 미치지 않음
total_cnt += x * (x-1)
#검은색 노드 체크
for i in range(1, n + 1):
if A[i] == 1:
for j in graph[i]:
if A[j] == 1:
total_cnt += 1
print(total_cnt)- 실내가 아닌 실외를 기준으로 dfs를 돌려야했던 코드
내 코드(60점 맞았던 코드)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input().strip())
A =[-1]
A = A + list(map(int,input().strip()))
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
u,v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
# 60 점 맞음
cnt = 0
def dfs(start):
global cnt
visited[start] = True
for i in graph[start]:
if visited[i] == False:
if A[i] == 1:
cnt +=1
continue
else:
dfs(i)
for j,k in enumerate(A):
visited = [False] *(N+1)
if k == 1:
dfs(j)
print(cnt) 문제 분류
1432 - 그래프 수정 - 플래티넘 4
문제 링크 - https://www.acmicpc.net/problem/1432
내 코드
import sys
from collections import deque
input = sys.stdin.readline
from heapq import heapify, heappop, heappush
N = int(input().strip())
graph = [[-1 for _ in range(N+1)]]
outdegree = [0 for _ in range(N+1)]
for _ in range(N):
seq = list(map(int,input().strip()))
graph.append([-1] + seq)
# V1 -> V2 : V2 > V1
#역방향 그래프
reversed_graphlist =[[] for _ in range(N+1)]
for i in range(1,N+1):
for j in range(1,N+1):
if graph[i][j] == 1:
reversed_graphlist[j].append(i)
outdegree[i] += 1
result = []
q = []
for i in range(1,N+1):
if outdegree[i] == 0:
heappush(q,-i)
while q:
cur = -heappop(q)
result.append(cur)
for x in reversed_graphlist[cur]:
outdegree[x] -= 1
if outdegree[x] == 0:
heappush(q,-x)
# 사이클 검사
if len(result) < N:
print(-1)
else:
## 출력
idx = [i for i in range(N,0,-1)]
for k,i in sorted(zip(result,idx)):
print(i,end=" ")
문제 분류
1948 - 임계경로 - 플래티넘 5
문제 링크 - https://www.acmicpc.net/problem/1948
내 코드
import sys
from collections import deque
input = sys.stdin.readline
n = int(input().strip())
m = int(input().strip())
graph = [[] for _ in range(n+1)]
indeg = [0 for _ in range(n+1)]
reversed_graph = [[] for _ in range(n+1)] # 역방향 추적용
for _ in range(m):
u,v,w = map(int,input().split())
graph[u].append((v,w))
reversed_graph[v].append((u,w))
indeg[v] += 1
start , end = map(int,input().split())
# 위상정렬해서 최장거리 찾기
q = deque()
q.append(start)
result = [start]
dist = [0 for _ in range(n+1)]
while q :
cur = q.popleft()
for i,wei in graph[cur]:
if dist[i] < dist[cur] + wei: # 최장거리 계산
dist[i] = dist[cur] + wei
indeg[i] -= 1
if indeg[i] == 0:
q.append(i)
result.append(i)
# 역추적해서 최장경로 찾아서 cnt 늘리기
visited = [False for _ in range(n+1)]
rq = deque()
rq.append(end)
visited[end] = True
count = 0
while rq:
now = rq.popleft()
for prev, weight in reversed_graph[now]:
if dist[now] == dist[prev] + weight:
count += 1
if not visited[prev]:
visited[prev] = True
rq.append(prev)
print(dist[end])
print(count)- 위상정렬을 통해 최장거리를 구하고
- 최장거리를 통해 역추적해서 최장거리의 경로를 구하는 문제
문제 분류
- 그래프 이론
- 그래프 탐색
- 방향 비순환 그래프
- 위상 정렬
-
DP의 개념이 필요한 문제들이 많았다고 생각한다. 얼른 다음주에 그리디,DP 하고싶다
-
문제풀이에 대한 아이디어를 떠올리기 힘들다.
위상정렬 indgree를 outdegree로 전환해서 푼다던가, 아침 산책의 실외 기준으로 카운트를 한다던가. 어렵다. -
내일 테스트 3문제 다 풀 수 있을까?
^_^