EDOC 2023-W 3회차 정모 (유니온 파인드 / 위상 정렬)

A. 여러분의 다리가 되어 드리겠습니다! (백준 17352번)

 

https://www.acmicpc.net/problem/17352

 

#python

from sys import stdin
import sys
sys.setrecursionlimit(100000)

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

n = int(stdin.readline())
parent = [i for i in range(n+1)]

for _ in range(n-2):
    a, b = map(int, stdin.readline().split())
    union(a, b)

x = find(1)
for i in range(2, n+1):
    if find(i) != x:
        print(x, i)
        break

(정답)

 

---

 

B. 선수과목 (Prerequisite) (백준 14567번)

 

https://www.acmicpc.net/problem/14567

 

#python

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
time = [0] * (n+1)
que = deque()

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)
    indegree[b] += 1

for i in range(1, n+1):
    if indegree[i] == 0:
        que.append(i)
        time[i] += 1

while que:
    now = que.popleft()
    for next in g[now]:
        time[next] = time[now] + 1
        indegree[next] -= 1
        if indegree[next] == 0:
            que.append(next)

for i in range(1, n+1):
    print(time[i], end=' ')

(정답)

 

---

 

C. 피리 부는 사나이 (백준 16724)

 

https://www.acmicpc.net/problem/16724

 

#python

from sys import stdin
import sys
sys.setrecursionlimit(100000)

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

n, m = map(int, stdin.readline().split())
parent = [i for i in range(n*m + 1)]

for i in range(n):
    input = stdin.readline()
    for j in range(m):
        if input[j] == 'U':
            union(i*m + (j+1), (i-1)*m + (j+1))
        elif input[j] == 'D':
            union(i*m + (j+1), (i+1)*m + (j+1))
        elif input[j] == 'L':
            union(i*m + (j+1), i*m + j)
        elif input[j] == 'R':
            union(i*m + (j+1), i*m + (j+2))

ans = []
for i in range(1, n*m + 1):
    ans.append(find(i))
print(len(set(ans)))

처음에는 런타임 에러도 아니고 틀렸습니다가 나오길래 왜지? 했는데 sys.setrecursionlimit(100000) 이거 추가하니까 맞았습니다가 나왔다. (정답)