n명의 사람을 0부터 n-1까지의 숫자로 표현하고, 친구 관계를 담은 리스트 friends가 주어졌다고 가정해 봅시다. 여기서 friends[i][0]과 friends[i][1]은 서로 친구인 두 사람을 의미합니다. 우리가 확인해야 할 것은 모든 사람이 최소 한 명 이상의 친구를 가지고 있는지 여부입니다.
예를 들어 n = 3이고 friends = [[0, 1], [1, 2]]라고 입력하면 출력은 True가 됩니다. 0번 사람은 1번 사람의 친구이고, 1번 사람은 0번과 2번 양쪽 모두의 친구이며, 2번 사람은 1번 사람의 친구이기 때문입니다. 즉, 세 사람 모두 최소 한 명의 친구가 존재합니다.
문제 해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- 크기가 n인 리스트 people을 만들고 0으로 초기화합니다.
- friends의 각 연결 관계(link)에 대해 다음을 수행합니다.
- people[link[0]]을 True로 설정합니다.
- people[link[1]]을 True로 설정합니다.
- people의 각 요소를 순회하면서 값이 비어 있는(즉, False 또는 0인) 경우가 있다면 False를 반환합니다.
- 모든 요소가 True라면 True를 반환합니다.
핵심 아이디어는 간단합니다. 친구 관계에 등장한 적이 있는 사람만 True로 표시되므로, 순회가 끝난 뒤 False로 남아 있는 사람이 있다면 그 사람은 친구가 없다는 뜻입니다. 이 방식의 시간 복잡도는 O(n + m)으로, n은 사람 수, m은 친구 관계의 수입니다.
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
예제 코드
class Solution: def solve(self, n, friends): people = [0 for i in range(n)] for link in friends: people[link[0]] = True people[link[1]] = True for person in people: if not person: return False return True ob = Solution() n = 3 friends = [ [0, 1], [1, 2] ] print(ob.solve(n, friends))
입력
3, [[0, 1],[1, 2]]
출력
True