• TOC {:toc}

이 글은 백준 온라인 저지의 1766번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.21

틀린 풀이입니다. 정답은 참고 답안을 참고해주세요.

단계 시작 시각 끝난 시각 걸린 시간
문제 이해 11:36:32 11:36:52
풀이 생각 1 11:37:04 11:44:20
풀이 생각 2 20:45:15 21:02:01
코딩 1 21:03:10 21:31:57
디버깅 1 21:36:50 21:43:45
디버깅 2 21:43:54 22:09:23
디버깅 3 23:21:41 23:31:18
디버깅 4 14:12:21 15:15:32 
import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
P = [[True, []] for _ in range(N + 1)]
res = []


def line_up(key):
    global P, res

    if not P[key][0]:
        return

    P[key][0] = False
    for x in sorted(P[key][1]):
        line_up(x)
    res.append(key)


for _ in range(M):
    f, b = map(int, input().split())
    P[b][1].append(f)

for i in range(1, N + 1):
    if P[i][0]:
        line_up(i)

print(*res)

아이디어 & 풀이

1부터 N까지 순서대로 출력하되 자신의 앞에 오는 수들의 리스트를 저장해서 출력하려고 했다.

  • 생기는 대소관계에 따라 특정 값이 최소값이 아닌 수의 앞으로도 이동할 수 있어서 일단 내 앞에 오는 모든 원소를 리스트에 유지해야한다.
  • 출력할 때 재귀로 각 원소를 순회하면서 res 담되, 중복으로 담기는 것을 방지할 수 있는 장치를 마련해야한다.
  • res 담은 여부를 확인할 수 있는 값을 가지면 된다.
    • True가 아직 담지 않은 상태(기본값)고, res에 담긴 값은 False로 바꿔서 중복을 방지한다.
  • 1부터 순차적으로 res에 담길 여부가 True이면 res에 원소를 담는 line_up 함수를 호출한다.
    • 담길 여부를 False로 바꾸고 자신의 앞에 있는 수의 리스트를 sorted 한 다음에 각 원소에 대해서 line_up을 호출하고 마지막에 자신을 추가한다.

디버그

  • 입력된 첫 번째 값이 두 번째 값보다 작을 수 있어서 첫 번째 값이 더 큰 경우만 실행하도록 조건을 추가했는데 또 틀렸다.
    • 작은 값이 큰 값보다 앞에 오는 것은 당연하기 때문에
  • 이미 자신보다 앞에 올 숫자들이 존재하는 두 값의 대소관계가 생겨서 값을 합칠때를 전혀 고려 못해서 틀렸고, 풀이를 다시 고안했다.
  • 그러고도 현재 틀린 상태.

피드백

통과 안 되는 케이스 찾아내고 올바르게 고쳐보기

참고 답안

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

N, M = map(int, input().split())
# 인덱스 i의 뒤에 오는 숫자들의 리스트를 저장한 리스트이다.
P = [[] for _ in range(N + 1)]
# 인덱스 i가 앞에서부터 몇 번째 숫자인지(degree)를 저장하는 리스트이다.
D = [0] * (N + 1)

heap = []
res = []

for _ in range(M):
    # 입력받은 두 수 a, b에 대해
    f, b = map(int, input().split())
    # 뒤에 오는 수 b를 P[f]에 추가하고
    P[f].append(b)
    # b의 degree를 1 증가시킨다
    D[b] += 1

for i in range(1, N + 1):
    # degree가 0(자신이 제일 앞)인 숫자만
    # 오름차순대로 heap에 집어 넣는다.
    if D[i] == 0:
        heappush(heap, i)

while heap:
    # 최솟값을 pop해서
    data = heappop(heap)
    # 결과에 더하고
    res.append(data)
    # 그 뒤에 오기로 한 원소에 대해
    for b in P[data]:
        # degree를 한 개 줄이고
        D[b] -= 1
        # degree가 0이면 heap에 집어 넣는다.
        # 자신보다 앞에 나와야 할 모든 숫자는 이미 나왔기 때문에
        # 나머지중 자신의 자리를 찾아가면 되는 것.
        if D[b] == 0:
            heappush(heap, b)

print(*res)

아이디어 & 풀이

heap을 사용해서 항상 최솟값을 유지하고 degree를 이용해서 중복을 관리한다.