[SWEA] #5643 키순서

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AWXQsLWKd5cDFAUo&categoryId=AWXQsLWKd5cDFAUo&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=PYTHON&select-1=4&pageSize=10&pageIndex=3

계획

단순히 한 방향으로 인접해있는 정점들에 대해 방문 여부만 확인하면 되는 게 아니라, 모든 점과 연결되는지를 확인해야 했다. 처음에는 모든 간선들의 방향을 뒤집으면 될까 싶었는데 진입 및 진출 차수를 모두 확인해야 할 것 같아서 아예 두 개의 인접 리스트를 만들고자 했다.

코드

def count_visited(arr, start):
    visited = [0] * (N + 1)
    stack = [start]
    while stack:
        now = stack.pop()
        for nxt in arr[now]:
            if not visited[nxt]:
                visited[nxt] = 1
                stack.append(nxt)

    return visited.count(1)


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    M = int(input())
    cnt = 0
    adj_out = [[] for _ in range(N + 1)]
    adj_in = [[] for _ in range(N + 1)]

    for _ in range(M):
        a, b = map(int, input().split())
        adj_out[a].append(b)
        adj_in[b].append(a)

    for student in range(1, N + 1):
        if count_visited(adj_out, student) + count_visited(adj_in, student) == N - 1:
            cnt += 1

    print('#{} {}'.format(tc, cnt))

풀이 방법

인접 정점을 카운트 할 수 있는 함수를 따로 작성했고, 모든 정점에 대해서 in & out 인접 리스트의 리턴값을 확인한 뒤 이 값이 정점의 개수와 같다면 결과를 +1 해주는 식으로 풀이했다.