EDOC 2023-W 2회차 과제 (유니온 파인드 / 위상 정렬)

08-2. 유니온 파인드

 

050. 집합의 표현 (백준 1717번)

 

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

 

from sys import stdin

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+1)]

for _ in range(m):
    x, a, b = map(int, stdin.readline().split())
    if x == 0:
        union(a, b)
    elif x == 1:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

find 연산이 진행될 때 경로 압축의 효과가 나타나서 시간 복잡도가 줄어드는 효과를 얻게 된다는 말이 텍스트로만 읽었을 때는 잘 이해가 되지 않았다. 그런데 실제로 코드를 작성해보니, find 연산 안에서 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경한다는 것을 알게 되어서 더 이해가 잘 되었다. (정답)

 

---

 

051. 여행 가자 (백준 1976번)

 

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

 

from sys import stdin

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())
m = int(stdin.readline())
city = []
parent = [i for i in range(n+1)]
possible = True

for _ in range(n):
    city.append(list(map(int, stdin.readline().split())))

plan = list(map(int, stdin.readline().split()))

for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            union(i+1, j+1)

for i in range(1, m):
    if find(plan[0]) != find(plan[i]):
        possible = False
        break

if possible:
    print("YES")
else:
    print("NO")

원래는 마지막에 find() 함수를 쓰는 대신 바로 parent 배열에 접근했다. 그런데 parent 배열에 직접 접근하는 방식은 동일한 부모 노드를 보장하지 않을 수 있다는 것을 알게 되었다. (정답)

추가로, 여기를 왜 한 쪽만 탐색하면 안 되는지를 모르겠다. 어차피 대각선 기준 대칭아닌가?
for i in range(n):
    for j in range(i, n):
        if city[i][j] == 1:
            union(i+1, j+1)

 

---

 

052. 거짓말 (백준 1043번)

 

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

 

from sys import stdin

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())
true = list(map(int, stdin.readline().split()))
party = []
for _ in range(m):
    party.append(list(map(int, stdin.readline().split())))
parent = [i for i in range(n+1)]
ans = 0

for i in range(m):
    for j in range(2, party[i][0]+1):
        union(party[i][1], party[i][j])

for i in range(m):
    possible = True
    for j in range(1, true[0]+1):
        if find(party[i][1]) == find(true[j]):
            possible = False
            break
    if possible:
        ans += 1
    
print(ans)

유니온 파인드를 떠올리기 어려웠던 문제. (정답)

 

---

08-3. 위상 정렬

 

053. 줄 세우기 (백준 2252번)

 

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

 

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)
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)

while que:
    new = que.popleft()
    print(new, end=' ')
    for x in g[new]:
        indegree[x] -= 1
        if indegree[x] == 0:
            que.append(x)

왜 visited 배열이 필요없나 했는데 사이클이 없으니 자기 자신한테 돌아올 일도 없으니 필요가 없는 것 같다. (정답)

 

---

 

054. 게임 개발 (백준 1516번)

 

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

 

from sys import stdin
from collections import deque

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

for i in range(1, n+1):
    data = list(map(int, stdin.readline().split()))
    time[i] = data[0]
    for j in range(1, len(data)-1):
        g[data[j]].append(i)
        indegree[i] += 1

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

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

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

처음 제출했던 코드. 이 때는 경로가 여러 개가 있을 수 있어서 특정 노드의 시간이 여러번 갱신될 수 있다는 점을 간과했다. (오답)

 

from sys import stdin
from collections import deque

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

for i in range(1, n+1):
    data = list(map(int, stdin.readline().split()))
    time[i] = data[0]
    for j in range(1, len(data)-1):
        g[data[j]].append(i)
        indegree[i] += 1

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

while que:
    new = que.popleft()
    for x in g[new]:
        indegree[x] -= 1
        if indegree[x] == 0:
            que.append(x)
            totalTime[x] = max(totalTime[x], totalTime[new] + time[x])

for i in range(1, n+1):
    print(totalTime[i])

그래서 totalTime[x] = max(totalTime[x], totalTime[new] + time[x]) 이렇게 수정해주었다. 그래도 여전히 틀렸다고 뜬다. (오답)

 

from sys import stdin
from collections import deque

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

for i in range(1, n+1):
    data = list(map(int, stdin.readline().split()))
    time[i] = data[0]
    for j in range(1, len(data)-1):
        g[data[j]].append(i)
        indegree[i] += 1

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

while que:
    new = que.popleft()
    for x in g[new]:
        indegree[x] -= 1
        if indegree[x] == 0:
            que.append(x)
        totalTime[x] = max(totalTime[x], totalTime[new] + time[x]) # 여기 수정

for i in range(1, n+1):
    print(totalTime[i])

질문게시판을 뒤져보니 특정 케이스에서 정답을 제대로 출력하지 않는데 통과가 되니 채점 데이터를 추가해달라는 1년 전의 글이 있었는데, 그 케이스에 걸리는 것이었다. ㅇㅅㅇ 어떻게 이럴수가... 아무튼 반례를 알게 되어서 그 반례를 한 단계 한 단계 쓰면서 확인해보니 totalTime을 업데이트 시키는 부분에 문제가 있었다. 진입 차수가 꼭 0이 아니더라도 항상 시간을 업데이트 해주어야 하는데, 그러지 않았어서 틀린 것이었다. (정답)

 

# input
5
10 -1
20 1 -1
30 2 -1
40 3 5 -1
100 -1

# my answer
10
30
60
100
100

# correct answer
10
30
60
140
100

참고용으로 내 반례를 적어둔다.

 

---

 

055. 임계경로 (백준 1948번)

 

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

 

from sys import stdin
from collections import deque

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

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

start, end = map(int, stdin.readline().split())

que.append(start)

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

visited = [False] * (n+1)
cnt = 0
que.clear()
que.append(end)

while que:
    now = que.popleft()
    for next in ig[now]:
        if time[next[0]] + next[1] == time[now]:
            cnt += 1
            if not visited[next[0]]:
                que.append(next[0])
                visited[next[0]] = True

print(time[end])
print(cnt)

넘 어려워서 거의 책 보면서 풀었다. 참고로 임계 경로란 여러 단계의 과정을 거치는 작업에서 그것을 완성하려면 여러 과정의 경로가 동시에 수행되어야 한다고 할 때, 그중 가장 긴 경로이다. 즉, 전체 공정 중 시간이 가장 많이 걸리는 경로이다. (정답)