📌 문제 탐색하기
👉 문제바로가기
컴퓨터의 수가 주어지고, 컴퓨터에는 1번부터 시작해서 각 번호가 붙여져있습니다. 네트워크 상에서 직접 연결되어있는 컴퓨터 쌍을 입력받은 후 1과 직접 또는 간접적으로 연결되어있는 컴퓨터의 수를 구하는 문제입니다.
📌 알고리즘 선택
DFS(Ddepth First Search)
우선 각 컴퓨터와 직접적으로 연결된 노드를 그래프 배열에 저장하고, 해당 노드들 각각을 기준으로하여 연결된 모든 노드들을 탐색하는 방식으로 문제를 풀면 되겠습니다.
문제에서 주어진 <그림1>을 예시로 들어보겠습니다.
- 노드 각각에 대해 직접적으로 연결된 노드를 찾습니다.
- 1은 2, 5노드와 연결
- 2는 1, 3, 5노드와 연결
- ...
- 7은 4노드와 연결
- 각 노드와 연결된 노드를 graph리스트에 저장합니다.
graph = [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]- 깊이 우선 탐색을 수행하며 1을 정점으로 설정하고 1에서 연결된 모든 노드들을 탐색하며 탐색을 한 경우 탐색여부를 True로 설정합니다.
이 문제는 연결된 노드를 찾고 해당 노드와 연결된 노드들을 반복해서 탐색해나가는 과정이므로 탐색하는 부분을 함수로 만들고, 정점과 연결된 모든 노드들을 탐색하면 되겠습니다. 연결이 되지 않은 부분은 탐색하지 않으니 탐색 여부가 False로 남아있을 것입니다.
탐색이 끝나면 정점을 제외하고 방문 여부가 True인 원소의 갯수를 구하면 됩니다.
시간복잡도
T+1번만큼 for문을 반복하면서 네트워크 연결쌍의 수(N)만큼 리스트 요소를 모두 탐색해야하므로 O((T+1)*N) = O(T*N)의 시간복잡도를 가집니다. 또한, 각 반복마다 list.remove()연산이 있기 때문에 최악의 경우 O(T)의 시간이 걸립니다.
따라서 그래프를 구축하는 부분에서 시간복잡도는 O(T^2*N)입니다.
dfs()에서는 각 노드와 연결된 모든 간선을 탐색해야 하므로 시간 복잡도는 O(T+N)입니다.
시간복잡도
• 그래프 구축:O(T^2 * N)
• DFS 탐색:O(T + N)
따라서, 시간 복잡도에 영향을 주는 요소 중 그래프 구축이 지배적이므로 최종 시간 복잡도는 O(T^2 * N)입니다. T는 100이고, N=T(T-1)/2이므로 최악의 경우 연산 횟수는 약 49,500,000회 입니다. 따라서 1초 안에 연산이 충분히 가능합니다.
📌 코드 설계하기
- 컴퓨터의 수, 네트워크 상에서 직접 연결되어있는 컴퓨터 쌍의 수, 네트워크 상에서 직접 연결되어있는 컴퓨터의 번호 쌍을 차례대로 Input받습니다.
- 1과 직접적으로 연결된 네트워크를 찾기 위해
bfs()를 호출합니다. - 1과 직접적으로 연결된 네트워크 각각에 대해서도
bfs()를 호출하여 네트워크를 찾습니다. - 1과 연결된 모든 네트워크의 방문 여부가 True가 될 경우 탐색을 종료하고, 방문 여부가 True인 노드의 갯수를 구하여 출력합니다.
📌 정답 코드
import sys
def dfs(graph, v, visited):
visited[v] = True
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
T = int(sys.stdin.readline()) #컴퓨터의 수
N = int(sys.stdin.readline()) #네트워크 상에서 직접 연결되어있는 컴퓨터 쌍의 수
network = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
graph = [[] for _ in range(T+1)] #인접 노드를 담은 리스트
visited = [False] * (T+1)
for i in range(T+1):
for j in range(N):
if i in network[j]:
graph[i].append(network[j][0])
graph[i].append(network[j][1])
graph[i] = list(set(graph[i])) #중복제거
graph[i].remove(i) #자기 자신의 숫자는 제거
dfs(graph, 1, visited)
print(visited.count(True) - 1) #시작노드(1)제외