AndroidTeacher

문제 설명

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

풀이 과정

위의 그림과 같은 상황이 있을 때,

4를 건설하기 위해서는 반드시 1 -> 2 -> 4의 순서로 건설되거나 1 -> 3 -> 4의 순서로 건설되어야 하기 때문에

선수 관계를 표현할 때 이용하는 위상정렬 알고리즘을 이용한다.

그리고, 1 -> 2 -> 4 경로는 건설시간이 총 21초가 걸리고

1 -> 3 -> 4 경로는 건설시간이 총 120초가 걸리는데

4를 건설하기 위해서는 2와 3이 모두 완료되어야 하기 때문에

2가 빨리 끝나더라도 3이 끝날 때 까지 기다려야 한다.

그래서 4를 건설하기 까지는 1 -> 3 -> 4의 소요시간인 120초가 소요된다.

이를 통해 알 수 있는 것은, 어느 한 지점에 들어오는 경로가 두 개 이상이라면 그 경로중 최댓값을 저장한다는 것이다.

이 부분은 DP를 이용해 두 경로 중 최댓값을 저장하는 방식을 이용하면 된다.

이 문제의 핵심은 위상정렬을 사용하되, 위상정렬을 하는 과정에서 DP를 이용해 최댓값을 저장해 나간다는 점이다.

이를 파이썬으로 작성한 코드는 다음과 같다.

코드 중 리스트d는 입력값으로 인덱스0부터 시작하므로

1부터 시작하는 인덱스와 맞춰주기 위해 i-1을 적용하였다.

import sys
from collections import deque

t = int(sys.stdin.readline())

for _ in range(t):
    n, k = map(int, sys.stdin.readline().rstrip().split())
    d = list(map(int, sys.stdin.readline().rstrip().split()))
    graph = [[] for _ in range(n + 1)]
    inDegree = [0 for _ in range(n + 1)]
    dp = [0 for _ in range(n + 1)]
    queue = deque()

    for i in range(k):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append(b)
        inDegree[b] += 1

    w = int(sys.stdin.readline().rstrip())

    for i in range(1, n + 1):
        if inDegree[i] == 0:
            queue.append(i)
            dp[i] = d[i - 1]

    while queue:
        tmp = queue.popleft()

        for i in graph[tmp]:
            inDegree[i] -= 1
            dp[i] = max(dp[i], dp[tmp] + d[i - 1])
            if inDegree[i] == 0:
                queue.append(i)

    print(dp[w])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

풀이 과정

이 문제는 일반적인 위상정렬이랑은 다르게, 간선처리 부분에 조금 신경을 써야 한다.

왜냐하면 둘의 상대적인 순위관계가 바뀌었을 때,

둘만의 상대적인 순위만 바뀐것이지, 그 외의 것들과는 순위관계가 바뀌지 않기 때문이다.

예를 들어, 5 -> 4 -> 3 -> 2 -> 1 로 순위가 주어졌을 때

(5번이 1등, 4번이 2등, 3번이 3등 ...)

5번은 4번보다 순위과 높고, 3번보다도 순위가 높은데

5번과 3번의 관계가 바뀌었다고 해서 5번이 4번보다 순위가 낮아지진 않는다.

그래서 각각의 원소들간의 모든 관계를 표시해야 하므로

5번은 4번,3번,2번,1번 보다도 순위가 높음을 표현하기 위해 모든 간선을 표시해야 한다.

이를 이용하여, 인접리스트로 그래프를 구현하게 되면

1 -> [ ]

2 -> [1]

3 -> [2, 1]

4 -> [3, 2, 1]

5 -> [4, 3, 2, 1]

으로 그래프가 형성이 되는데,

5번과 3번의 상대적인 순위 관계가 바뀐다면,

5번그래프에 3번을 빼주어야 하고

3번 그래프에 5를 넣어주어야 한다.

이 때, 3번으로 들어오는 간선이 하나 줄어들고, 5번으로 들어오는 간선이 하나 늘어났으므로

차수(indegree)도 변경을 해주어야 한다.

그리고, 문제에서 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다고 했는데

일관성이 없는 경우는 사이클이 발생하는 경우를 이야기한다.

즉, 원소들간의 관계가 잘못 표현되어 그래프에 사이클이 발생하여 위상관계를 표현할 수 없기 때문에

이 부분도 예외처리를 해주어야 한다.

예를 들어, 큐에 존재하는 원소의 개수가 2개가 된다던지, 1개도 없는 경우가 발생하는 경우이다.

직접 그림을 그려보면 알겠지만,

사이클이 발생하면 큐에 아무원소도 들어갈 수 없다.

또한, 한 번에 2개 이상의 원소가 들어간다는 것은

진입차수가 0인 원소가 두개 이상이 되므로 순위를 정할 수 없는 경우가 된다.

마지막으로, 확실한 순위를 찾을 수 없는 경우는 발생하지 않으므로 신경을 쓰지 않아도 된다.

from collections import deque
import sys

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())

    graph = [[] for _ in range(n + 1)]
    inDegree = [0 for _ in range(n + 1)]
    queue = deque()
    answer = []
    flag = 0

    team = list(map(int, sys.stdin.readline().rstrip().split()))

    for j in range(n - 1):
        for k in range(j + 1, n):
            graph[team[j]].append(team[k])
            inDegree[team[k]] += 1

    m = int(sys.stdin.readline())
    for j in range(m):
        first, second = map(int, sys.stdin.readline().rstrip().split())
        flag = True

        for k in graph[first]:
            if k == second:
                graph[first].remove(second)
                inDegree[second] -= 1
                graph[second].append(first)
                inDegree[first] += 1
                flag = False

        if flag:
            graph[second].remove(first)
            inDegree[first] -= 1
            graph[first].append(second)
            inDegree[second] += 1

    for j in range(1, n + 1):
        if inDegree[j] == 0:
            queue.append(j)

    if not queue:
        print("IMPOSSIBLE")
        continue

    result = True
    while queue:
        if len(queue) > 1:
            result = False
            break

        tmp = queue.popleft()
        answer.append(tmp)
        for j in graph[tmp]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                queue.append(j)
            elif inDegree[j] < 0:
                result = False
                break

    if not result or len(answer) < n:
        print("IMPOSSIBLE")
    else:
        print(*answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

풀이 과정

전형적인 위상정렬 문제이다.

A번 학생이 B번 학생보다 반드시 먼저 앞에와야 하는 상황이 주어지기 때문에,

A -> B를 만족시키면서 정렬을 해야 하기 때문이다.

위상정렬의 과정은 다음과 같다.

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입
4. 이후 2~3의 과정을 반복

이를 해당 문제에 적용해보자.

다음과 같은 입력이 주어졌다고 해보자.

학생들은 4명이 있고 다음과 같은 조건이 주어졌다.

• 4 -> 2
• 3 -> 1

4번은 반드시 2번앞에 와야 하므로 4 -> 2 로의 간선이 존재하므로 2번의 진입차수는 1이 되며

3번은 반드시 1번앞에 와야 하므로 3 -> 1 로의 간선이 존재하므로 1번의 진입차수는 1이 된다.

먼저, 진입차수가 0인 3번과 4번을 큐에 넣은 다음 ( 3번과 4번을 먼저 줄 세우겠다는 뜻 )

큐에서 먼저 3을 꺼내 3과 연결된 간선들을 제거한다.

(3은 이미 줄을 섰으므로 3 다음에 와야 할 것들은 언제와도 무방)

따라서 위상정렬로 위의 방식대로 해결한 풀이는 다음과 같다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]
inDegree = [0 for _ in range(n+1)]
queue = deque()
answer = []

for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    inDegree[b] += 1

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

while queue:
    tmp = queue.popleft()
    answer.append(tmp)
    for i in graph[tmp]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            queue.append(i)

print(*answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

풀이 과정

이 문제를 풀기전에 먼저, 위상정렬에 대해 살펴보자.

위상정렬이란, 사이클이 없는 방향그래프(DAG) 에서 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 정해주는 알고리즘이다.

이 문제처럼, 어떤 문제를 풀 때 그 문제의 선수문제가 있는 경우 선수문제를 반드시 먼저 풀어야 하기 때문에

위상정렬을 이용해야 한다.

위상정렬의 전체적인 과정은 다음과 같다.

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입
4. 이후 2~3의 과정을 반복

이 때, 모든 원소를 방문하기 전에 큐가 비게된다면 사이클이 존재하는 그래프이며

사이클이 존재하는 그래프는 위상정렬을 적용할 수 없다.

아니라면, 큐에서 꺼낸 순서가 위상정렬의 결과가 되는 것이다.

그럼, 이 위상정렬을 이용하여 문제를 해결해보자.

예시로 다음과 같은 상황이 있다고 하자.

• 4 -> 1
• 5 -> 1
• 2 -> 5
• 3 -> 5

위의 상황은 4,5번 문제를 풀고 1번 문제를 풀어야 하며 2,3번 문제를 풀고 5번 문제를 풀어야 하는 상황이다.

그래서 1번의 진입차수는 2가 되고

5번의 진입차수도 2가 된다.

이 때, 문제에서 가능한 앞 번호의 문제부터 풀어야 한다고 했으므로

위상정렬의 큐를 우선순위 큐를 이용하자.

우선순위 큐 대신 큐에서 min을 이용해 값을 꺼내려고 한다면

시간복잡도가 훨씬 증가하기 때문에 우선순위 큐를 이용하는 것이 좋다.

번호대로라면 1번 문제부터 풀고 싶겠지만,

1번문제는 반드시 4, 5번 문제를 먼저 풀고나서 풀어야 하기 때문에

2번으로 넘어가자.

2번문제에도 선수문제가 존재한다면 우선순위를 뒤로 넘겨야 하겠지만

2,3,4 번 문제는 선수문제가 없기 때문에 그대로 순서대로 풀면 된다.

2,3,4번을 푼 상태에서 이제 5번을 풀려고 보니 5번은 선수문제가 있다.

2,3번 문제가 5번의 선수문제인데 앞에서 이미 풀었으므로 5번을 풀자.

(여기서 선수문제를 푼 것은 진입차수를 - 해줌으로써 표시할 수 있다.)

그리고 남은 1번 문제도 선수문제들을 모두 풀었으므로 1번을 풀면 된다.

(1번 문제의 진입차수가 2에서 - 2가 되어 0으로 변함)

그래서 정답은 2, 3, 4, 5, 1이 된다.

[위상정렬 성공 코드]

import sys
import heapq

n, m = map(int, sys.stdin.readline().rstrip().split())

answer = []
graph = [[] for _ in range(n + 1)]
inDegree = [0 for _ in range(n+1)]
queue = []


for i in range(m):
    first, second = map(int, sys.stdin.readline().rstrip().split())
    graph[first].append(second)
    inDegree[second] += 1

for i in range(1, n + 1):
    if inDegree[i] == 0:
        heapq.heappush(queue, i)

while queue:
    tmp = heapq.heappop(queue)
    answer.append(tmp)
    for i in graph[tmp]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            heapq.heappush(queue, i)


print(" ".join(map(str, answer)))

이 문제를, 위상정렬을 적용하기 전에는

우선순위 큐와 DFS를 이용해서 접근을 했었다.

이 방식으로는 예외가 되는 케이스가 너무 많이 발생하여 결국 해결하지 못하였다.

그 코드는 다음과 같다.

[DFS + 우선순위 큐 : 실패 코드]

import sys
import heapq

n, m = map(int, sys.stdin.readline().rstrip().split())

answer = []
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)


def popElement(num):
    while graph[num]:
        next = heapq.heappop(graph[num])

        if not visited[next]:
            popElement(next)
            visited[next] = True
            answer.append(next)


for i in range(m):
    first, second = map(int, sys.stdin.readline().rstrip().split())
    heapq.heappush(graph[second], first)

for i in range(1, n + 1):
    if not visited[i]:
        popElement(i)

    if not visited[i]:
        visited[i] = True
        answer.append(i)


print(" ".join(map(str, answer)))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !