문제
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한 사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
문제를 보고 든 생각
최근에 풀었던 연결 요소의 개수를 구하는 문제가 떠올랐다.
한편으로는 문제가 잘 이해가 안 됐다.
예제를 봐도 뭘 요구하는지 파악이 안 됐다.
나의 아이디어
0이 아닌 1이 있는 곳을 기준으로 동서남북을 탐색하여 덩어리의 개수를 구하는 문제라고 생각했다.
그래서 평범하게 그런 식으로 구현을 했고 bfs를 활용했다.
결과
코드의 기록이 남아 있지 않아 아쉽지만, 1문제 맞았다.
나머지에서는 모두 오답 처리가 됐다.
개선
문제만 알면 풀 수 있을 것 같아서 문제를 이해해보려고 검색을 마구마구 했다.
그러다가 얻은 힌트는 인풋은 양방향 그래프이므로 양방향으로 연결된 곳들을 모두 탐색해야 한다는 것이었다.
양방향 그래프를 처리해줄 때는 보통
graph[u].append(v)
graph[v].append(u)
이런 식으로 처리해주어 구현했는데,
이미 인풋이 들어와있는 상황에서 양방향 그래프 탐색을 구현하라는 건 처음이어서 뭘 어떻게 해야하는지 가늠이 안 갔다.
검색을 통해 알게 된 내용
검색을 통해서 구현 코드를 살펴보니 이미 내가 어느 정도 알고 있었던 방식이었다.
그래서 풀이를 이해할 수 있었다는 거에 다행이라고 생각했다.
문제를 완전히 이해했었다면 해결해낼 수 있었을까?
검색을 통해 알게 된 풀이
visited = [False for _ in range(n)]
# 양방향으로 설계
def networking(computers, v, visited, n):
visited[v] = True
for node in range(n):
if not visited[node] and computers[node][v] == 1:
visited[node] = True
networking(computers, node,visited,n)
count = 0
for v in range(n):
if not visited[v]:
networking(computers, v, visited, n)
print(visited)
count += 1
print(count)양방향으로 탐색하게끔 구현하는 건 dfs 함수 안의 for문이 핵심인 것 같다.
보통 for문을 돌릴 때 그래프 안에 들어있는 노드들을 가지고 돌리는데
여기에서는 컴퓨터의 개수를 나타내는 n을 범위로 하여 for문을 돌린다는 게 차이점이었다.
앞으로는 양방향 그래프를 구현하라고 하면 우선적으로 dfs 함수 안에서 그래프의 요소를 가지고 for문을 돌려 구현하라는 말이라고 이해하면 될 것 같다.
개인적으로 bfs로도 풀 수 있을 것 같은 느낌이 들어서, 위를 활용하여 bfs로도 풀어봤다.
from collections import deque
visited = [False for _ in range(n)]
# 양방향으로 설계
def networking(computers, v, visited, n):
q = deque([v])
visited[v] = True
while q:
now = q.popleft()
for node in range(n):
if not visited[node] and computers[node][now] == 1:
visited[node] = True
q.append(node)
count = 0
for v in range(n):
if not visited[v]:
networking(computers, v, visited, n)
print(visited)
count += 1
print(count)느낀 점
1. 문제를 이해하는 능력도 문제를 해결하는 데 필요한 중요한 능력인 걸 깨달았다.
2. 양방향 그래프를 탐색하는 방법은 그래프의 요소를 가지고 for문을 돌리는 과정이 수반된다는 걸 깨달았다.
