문제
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 예
| n | computers | return |
|---|---|---|
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
풀이
- 1 <= n <= 200인 자연수 이므로 DFS, BFS 모두 가능
- 컴퓨터들의 연결 정보가 2차원 배열로 주어지지만 이를 1차원으로 축소하는게 쉽게 푸는 핵심
Go
DFS
func dfs(computers [][]int, visited []int, now int) {
visited[now] = 1
for idx, connect := range computers[now] {
if connect == 1 && visited[idx] == 0 {
dfs(computers, visited, idx)
}
}
}
func solution(n int, computers [][]int) int {
cnt := 0
visited := make([]int, n)
for i := 0; i < n; i++ {
if visited[i] == 0 {
dfs(computers, visited, i)
cnt++
}
}
return cnt
}테스트 1 〉 통과 (0.00ms, 4.17MB)
테스트 2 〉 통과 (0.00ms, 4.2MB)
테스트 3 〉 통과 (0.00ms, 4.2MB)
테스트 4 〉 통과 (0.00ms, 3.54MB)
테스트 5 〉 통과 (0.00ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 3.55MB)
테스트 7 〉 통과 (0.00ms, 4.22MB)
테스트 8 〉 통과 (0.00ms, 4.24MB)
테스트 9 〉 통과 (0.00ms, 4.43MB)
테스트 10 〉 통과 (0.00ms, 4.2MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 3.53MB)
테스트 13 〉 통과 (0.01ms, 4.22MB)- 방문 여부를 기록하는 배열(
visited)을 생성한다. - 순차적으로 방문하지 않은 컴퓨터를 찾는다.
- 재귀 함수 내에서 해당 컴퓨터의 방문 여부를 체크한다.
- 해당 컴퓨터와 연결되어 있으면서 아직 방문하지 않은 다음 컴퓨터를 찾아 위 작업을 반복한다.
- 네트워크 갯수를 증가시키고 2번부터 반복한다.
BFS
func solution(n int, computers [][]int) int {
var cnt int
visited := make([]int, n)
for idx, visit := range visited {
if visit == 0 {
q := []int{idx}
for len(q) != 0 {
now := q[0]
q = q[1:]
visited[now] = 1
for i, connect := range computers[now] {
if connect == 1 && visited[i] == 0 {
q = append(q, i)
}
}
}
cnt++
}
}
return cnt
}테스트 1 〉 통과 (0.00ms, 3.79MB)
테스트 2 〉 통과 (0.00ms, 4.22MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 4.09MB)
테스트 5 〉 통과 (0.00ms, 3.53MB)
테스트 6 〉 통과 (0.04ms, 3.57MB)
테스트 7 〉 통과 (0.00ms, 3.53MB)
테스트 8 〉 통과 (0.02ms, 3.59MB)
테스트 9 〉 통과 (0.02ms, 4.22MB)
테스트 10 〉 통과 (0.03ms, 4.2MB)
테스트 11 〉 통과 (0.10ms, 4.19MB)
테스트 12 〉 통과 (0.06ms, 4.19MB)
테스트 13 〉 통과 (0.04ms, 3.79MB)Python
DFS
def solution(n, computers):
answer = 0
visited = [0] * n
def dfs(now):
nonlocal computers, visited
visited[now] = 1
for idx, connect in enumerate(computers[now]):
if connect == 1 and visited[idx] == 0:
dfs(idx)
return
for idx in range(n):
if visited[idx] == 0:
dfs(idx)
answer += 1
return answer테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.06ms, 10.2MB)
테스트 4 〉 통과 (0.03ms, 10.2MB)
테스트 5 〉 통과 (0.01ms, 10.3MB)
테스트 6 〉 통과 (0.27ms, 10.2MB)
테스트 7 〉 통과 (0.02ms, 10.1MB)
테스트 8 〉 통과 (0.19ms, 10.1MB)
테스트 9 〉 통과 (0.12ms, 10.1MB)
테스트 10 〉 통과 (0.07ms, 10.2MB)
테스트 11 〉 통과 (0.85ms, 10.2MB)
테스트 12 〉 통과 (0.41ms, 10.2MB)
테스트 13 〉 통과 (0.41ms, 10.1MB)BFS
def solution(n, computers):
answer = 0
visited = [0] * n
for idx, visit in enumerate(visited):
if visit == 1:
continue
q = [idx]
while len(q) != 0:
now = q.pop(0)
visited[now] = 1
for j, connect in enumerate(computers[now]):
if connect == 1 and visited[j] == 0:
q.append(j)
answer += 1
return answer테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.3MB)
테스트 3 〉 통과 (0.09ms, 10.3MB)
테스트 4 〉 통과 (0.09ms, 10.2MB)
테스트 5 〉 통과 (0.01ms, 10.1MB)
테스트 6 〉 통과 (0.57ms, 10MB)
테스트 7 〉 통과 (0.02ms, 10.2MB)
테스트 8 〉 통과 (0.28ms, 10.2MB)
테스트 9 〉 통과 (0.21ms, 10.3MB)
테스트 10 〉 통과 (0.31ms, 10.1MB)
테스트 11 〉 통과 (2.29ms, 10.3MB)
테스트 12 〉 통과 (1.00ms, 10.2MB)
테스트 13 〉 통과 (0.42ms, 10.2MB)
🖥️