[백준: Python] 2458 - 키 순서

[문제]

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

처음에는 어떻게 풀어야 할지 고민했습니다.

 

그런데 그래프 이미지 하단에 설명을 보고 연결된 그리고 연결한 노드의 수가 n - 1일 때 등수를 알 수 있다는 것을 알게 됐고, 진입 노드의 수 + 진출 노드의 수를 계산하면 답을 구할 수 있겠다고 생각했습니다.

 

이를 위해 진입 그래프와 진출 그래프를 만들고 두 번의 DFS를 수행했습니다. 굉장히 부르트포스한 방법인데, Python 기준 3000ms대로 풀이가 통과됐고, 입력을 sys를 받았을 때 위와 같은 시간대로 통과됐습니다.

---

[초기화]

    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.info = [tuple(map(int, input().split())) for _ in range(self.m)]
        self.answer = 0

---

[풀이]

    def search(self, graph: dict[int, list], degree: list[int], visited: list[bool], current: int):
        for nxt in graph[current]:
            if not visited[nxt]:
                visited[nxt] = True
                degree[nxt] += 1
                self.search(graph, degree, visited, nxt)
        return

현재 노드를 기준으로 연결된 노드를 모두 탐색합니다.

 

이때 진입 및 진출 노드의 수를 따로 관리를 하게 됩니다.

    def solve(self):
        in_graph = defaultdict(list)
        out_graph = defaultdict(list)
        in_degree = [0] * (self.n + 1)
        out_degree = [0] * (self.n + 1)

        for a, b in self.info:
            in_graph[b].append(a)
            out_graph[a].append(b)

        for i in range(1, self.n + 1):
            visited = [False] * (self.n + 1)
            visited[i] = True
            self.search(in_graph, in_degree, visited, i)
            self.search(out_graph, out_degree, visited, i)

        for i in range(1, self.n + 1):
            if in_degree[i] + out_degree[i] == self.n - 1:
                self.answer += 1

두 번의 DFS를 통해 진입 및 진출 노드의 수를 구했다면, 순차적으로 순회하며 각 노드들의 합이 n - 1인지 확인하며 정답을 갱신합니다.

---

[전체 코드]

from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()


class Main:
    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.info = [tuple(map(int, input().split())) for _ in range(self.m)]
        self.answer = 0

    def search(self, graph: dict[int, list], degree: list[int], visited: list[bool], current: int):
        for nxt in graph[current]:
            if not visited[nxt]:
                visited[nxt] = True
                degree[nxt] += 1
                self.search(graph, degree, visited, nxt)
        return

    def solve(self):
        in_graph = defaultdict(list)
        out_graph = defaultdict(list)
        in_degree = [0] * (self.n + 1)
        out_degree = [0] * (self.n + 1)

        for a, b in self.info:
            in_graph[b].append(a)
            out_graph[a].append(b)

        for i in range(1, self.n + 1):
            visited = [False] * (self.n + 1)
            visited[i] = True
            self.search(in_graph, in_degree, visited, i)
            self.search(out_graph, out_degree, visited, i)

        for i in range(1, self.n + 1):
            if in_degree[i] + out_degree[i] == self.n - 1:
                self.answer += 1

        print(self.answer)


problem = Main()
problem.solve()

---