2023년 9월 1일 알고리즘 문제풀이
문제 1 백준 2252
1차 시도
위상정렬에 대한 개념을 다 까먹어서 어떻게 풀지 감이 안왔다.. 해서 위상정렬을 공부해보고 풀었다.
위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 작업을 차례대로 수행할 때 순서를 결정하는 방법이다. 이번 문제도 어떤 학생들은 순서에 맞게 배열해야 하니 위상 정렬 문제로 풀 수있다.
위상 정렬의 과정은 다음과 같다.
- 방향이 있는 간선들의 정보가 주어지면 인접그래프를 만든다.
- 정점의 번호를 index로 하는 배열을 만든 후 해당 정점이 도착지가 되는 간선이 있을 떄마다 정점의 값을 1 올린다. 이 정점의 값이 진입차수를 의미한다. 해당 정점으로 진입하는 간선이 몇개인지를 나타내는 것이다.
- 위 과정이 완료되면 값이 0인 정점은 큐에 삽입한다.
- 큐에서 한 정점씩 꺼내어 해당 정점과 연결된 간선을 모두 제거한다.
- 이 과정에서 값이 0이 된 정점은 큐에 삽입하고 과정을 반복한다.
- 큐에서 꺼내지는 순서가 작업의 순서이다.
이 문제에 대입해보면, 문제의 입력값에서 순서가 있는 학생이 주어진다. 학생을 정점이라 생각하고 배열의 선후관계를 간선의 방향이라고 생각하면 된다. 코드는 다음과 같다.
나의 생각
결과
이해
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
level = [0 for _ in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
level[b] += 1
arr = deque()
for i in range(1, n+1):
if not level[i]:
arr.append(i)
ans = []
while arr:
now = arr.popleft()
ans.append(now)
for i in graph[now]:
level[i] -= 1
if not level[i]:
arr.append(i)
print(*ans)
문제 2 백준 2637
1차 시도
나의 생각
기존 위상정렬에서 진입차수를 나타내기 위한 배열과 필요한 부품의 갯수를 나타내는 배열을 분리했다. 위상정렬의 로직은 유지하고 똑같이 모든 값이 0이고 원소가 n+1개인 배열 level 과 cost를 만들었다. level은 진입차수를 나타내는데 사용하였다. 완제품은 1개가 필요하기 때문에 cost배열의 마지막의 값만 1로 바꿔주었다.
여기서 출발지와 도착지, 비용은 완성 부품과 필요 부품, 갯수를 의미한다고 생각하면 이해가 쉬울 것이다. 예를들어서 5번 제품을 만드는데 1번 제품 2개가 쓰인다면 입력값에 분명5 1 2 가 있을 것이다. 이를 1번 정점에서 5번 정점으로 가는데 비용 2가 필요하다고 생각하면 기존 위상정렬 문제와 같다는 것을 알 수 있다.. 도착 정점 = 완성 부품, 출발 정점 = 필요 부품, 비용 : 부품 필요 갯수.
이제 코드의 진행대로 문제 풀이 방법을 더 자세하게 설명해보겠다. 나는 이해를 돕기 위해 정점이 아닌 부품이라는 단어를 써서 설명해보겠다.
우선 말했던대로 모든 값이 0인 배열을 2개 만든다. 위상정렬의 진입차수 표시를 위한 배열 level과 부품의 갯수를 나타낼 cost이다. 완제품은 1개만 있으면 되기 때문에 cost[n]의 값만 1로 설정해주었다.
주어진 입력값을 순회하면서 인접그래프를 만들었다. 단, 필요 부품 이름과 갯수를 배열로 묶어 넣었다. 그리고 기존 위상정렬과 마찬가지로 완제품의 진입차수를 1 더해주면서 level 배열을 업데이트하였다.
기존에는 진입차수가 0인 정점들을 큐에 넣었다. 하지만 난 이번 문제에서 완제품을 의미하는 n을 넣고 시작했다. 이번 문제는 결국 기본 부품이 몇개가 필요한지를 파악하는 문제이다. 즉, 완제품 1개를 모두 분해하면 답을 알 수 있는 문제이다. 이러한 이유로 큐에 가장 큰 값이자 완제품인 n을 넣은 것이다.
for 반복문을 통해 완제품을 만들기 위한 필요부품과 갯수가 i로 표시된다. i[0]을 index로 하는 level의 원소는 진입차수를 뜻하므로 -1 해준다. 해당 index 값을 가지는 cost 의 원소값은 필요한 갯수를 의미한다. 여기서 i[1]을 그냥 더하지 않고 `cost[now]`값을 곱해서 더해준다. i[1]이 의미하는 것은 now라는 부품 1개를 만들때 필요한 것이다. 완제품을 만들기 위해서는 cost[now]값이 필요하기 때문에 곱해주는 것이다.
이 과정이 모두 끝나면 출력해야 하는데, graph가 없는 것만 출력해야한다. graph는 해당 부품을 만들기 위해 필요한 부품들의 번호와 갯수를 나타낸다. 이것이 없다는 것은 만들기 위해 다른 부품이 필요하지 않은 기본 부품이라는 의미이기 떄문이다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
from collections import deque
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
level = [0 for _ in range(n+1)]
cost = [0 for _ in range(n+1)]
cost[n] = 1
for _ in range(m):
x,y,k = map(int,sys.stdin.readline().split())
graph[x].append([y,k])
level[y] += 1
arr = deque()
ans = []
arr.append(n)
while arr:
now = arr.popleft()
for i in graph[now]:
cost[i[0]] += i[1]*cost[now]
level[i[0]] -= 1
if not level[i[0]]:
arr.append(i[0])
for i in range(1,n+1):
if not graph[i]:
print(i,cost[i])
문제 3 백준 1432
1차 시도
나의 생각
여전히 위상정렬 문제이다. 연결된 간선의 출발 정점과 도착 정점의 번호는 도착 정점의 번호가 더 커야한다고 한다. 따라서 출발정점은 n번이 될 수 없다. n보다 큰 정점은 없기 때문이다. 만약 더이상 출발정점이 될 수없는 정점이 있다면 그 정점은 최대한 큰 값을 가져야 한다. 그래야 뒤에 설정할 정점들에게 새로운 번호를 제공할 수 있다. 예를 들어, 출발지 역할을 하지 않고 도착지로서만 기능하는 정점에게 2라는 새로운 번호를 붙인다면? 2라는 새로운 번호를 얻은 정점으로 간선을 보낼수 있는 정점은 1 밖에 없다. 새로운 번호를 5로 한다면? 1,2,3,4 총 4가지 방법이 있게 된다.
즉, 그동안 위상 정렬은 출발하는 처음에서 끝까지를 관점으로 보고 있었다면, 이번 문제는 끝에서 처음으로 정 반대로 본다고 생각하면 된다. 그동안 간선을 나타내는 인접리스트는 출발지를 기준으로 어디로 갈 수 있는지를 나타내었다면 이번 문제에서는 도착지를 기준으로 이 정점으로 간선을 보내는 출발지들이 누구인지를 표시한다. 또한 해당 정점으로 간선을 보내는 출발 정점들의 갯수를 진입 차수라는 이름으로 표시하였다면, 이번에는 해당 정점에서 몇군데로 간선을 보내는지 진출차수를 표시하면 된다.
진출차수가 0이라는 의미는 더이상 이 정점은 출발지로서 간선을 보유하고 있지 않다는 의미이다. 문제에서 출발 정점이 도착정점보다 숫자가 작아야 한다고 했으니, 진출차수가 0인 정점은 더이상 누구보다 작아야하는지 조건이 존재하지 않다는 뜻이다. 따라서 현재 줄 수 있는 숫자 중 가장 큰 수를 주면 된다.
만약 진출차수가 0인 정점이 2개라면? 둘 중 숫자가 더 큰 정점을 먼저 처리해야 한다. 이것을 위해서는 최대힙을 사용하였다. 그동안 풀었던 위상정렬의 관점을 물구나무서서 보면 된다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
tmp = []
for _ in range(n):
tmp.append(list(sys.stdin.readline().rstrip()))
graph = [[] for _ in range(n+1)]
level = [0 for _ in range(n+1)]
arr = []
ans = [0 for _ in range(n+1)]
cnt = n
for i in range(n):
for j in range(n):
if tmp[i][j] == '1':
graph[j+1].append(i+1)
level[i+1] += 1
if not level[i+1]:
heappush(arr, -1*(i+1))
while arr:
now = -1*heappop(arr)
ans[now] = cnt
cnt -= 1
for i in graph[now]:
level[i] -= 1
if not level[i]:
heappush(arr, -1*i)
if 0 in ans[1:]:
print(-1)
else:
print(*ans[1:])
