1. 문제 소개

2092. Find All People With Secret

2. 나의 풀이

이 문제가 어려움 난이도인 이유는 아무래도 시간제한인 것 같다.
처음에는 아주 단순하게 생각했는데, 시행착오를 조금 겪은 이후에는 bfs를 떠올렸다.
그리고 시간초과로 인해 틀리고 말았다.

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        graph = [list() for _ in range(n+1)]

        for x, y, t in meetings:
            graph[x].append((t, y))
            graph[y].append((t, x))

        earliest = [inf] * n
        earliest[0] = 0
        earliest[firstPerson] = 0

        q = deque()
        q.append((0, 0))
        q.append((0, firstPerson))

        while q:
            time, person = q.popleft()
            for t, nxt in graph[person]:
                if t >= time and earliest[nxt] > t:
                    earliest[nxt] = t
                    q.append((t, nxt))
        
        return [i for i in range(n) if earliest[i] != inf]

3. 다른 풀이

다른 풀이는 Union-Find(DSU)였다.
사실 아직도 잘 이해하지 못해서 모르는 것이 많다.

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        meetings.sort(key=lambda x: x[2])                      # 시간 t 기준으로 정렬(시간 그룹 단위 처리 목적)
        parent = list(range(n))                                # DSU(Union-Find) 부모 배열 초기화
        know = [False] * n                                     # know[i]: i가 비밀을 알고 있는지 여부
        know[0] = know[firstPerson] = True                     # 시간 0에 0과 firstPerson은 비밀을 앎

        def find(x):
            if parent[x] != x:                                 # 경로 압축을 위한 재귀 탐색
                parent[x] = find(parent[x])                    # 루트로 압축
            return parent[x]                                   # 루트 반환

        def union(a, b):
            pa, pb = find(a), find(b)                          # 각 노드의 루트 찾기
            if pa != pb:                                       # 서로 다른 집합이면
                parent[pb] = pa                                # 한쪽 루트를 다른 쪽에 붙여 합치기(랭크 미사용)

        i = 0                                                  # meetings 순회 인덱스
        while i < len(meetings):                               # 모든 만남을 처리할 때까지 반복
            t = meetings[i][2]                                 # 현재 시간 그룹의 시간 t
            temp = []                                          # 현재 시간 t에 등장한 사람들을 모으는 리스트

            j = i                                              # 같은 시간 t 구간의 끝을 찾기 위한 포인터
            while j < len(meetings) and meetings[j][2] == t:   # 같은 시간 t인 meetings를 모두 처리
                union(meetings[j][0], meetings[j][1])          # 시간 t 내에서 연결(동일 시간 컴포넌트 구성)
                temp += meetings[j][:2]                        # (x, y)를 temp에 추가(해당 시간에 관여한 사람 수집)
                j += 1                                         # 다음 meeting으로 이동

            for x in temp:                                     # 시간 t에 등장한 사람들을 순회
                if know[x]:                                    # 그 사람이 이미 비밀을 알고 있다면
                    know[find(x)] = True                       # 그 사람의 컴포넌트 루트에 "비밀을 아는 컴포넌트" 표시

            for x in temp:                                     # 다시 시간 t 등장 인원 순회
                know[x] |= know[find(x)]                       # 컴포넌트 루트가 비밀을 알면 구성원도 비밀을 알게 함

            for x in temp:                                     # 시간 t 처리가 끝났으므로
                parent[x] = x                                  # DSU 연결을 초기화(시간대를 넘어 연결이 유지되지 않게 함)

            i = j                                              # 다음 시간 그룹으로 이동

        return [i for i in range(n) if know[i]]                # 최종적으로 비밀을 아는 사람 인덱스 목록 반환

4. 마무리

언뜻 보기에는 쉬운 문제인 줄 알았지만 그렇지 않았다.