문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
키포인트 정리
-
서로 연결 되어 있는 것들은 같은 네트워크 상에 있다.
- A와 B가 연결 되어있다면 1개로 생각한다.
-
먼저 지나가지 않은 부분이 있는지 N개 만큼 확인해본다.
-
지나가지 않았던 부분을 체크해 카운트를 세면 중복을 제거한 값이 나온다.
- A와 B가 연결되어있다면 A에서 이미 B는 지나간 것으로 체크가 되어 중복 제거가 가능.
-
만약 지나가지 않았다면 그 부분을 찾아 서로 연결되어있는 부분이 있는지 살펴본다.
- 서로 연결 되어 있는 부분이 있다면 그 부분을 방문했는지 체크해볼 필요가 있다.
풀이
키포인트에 따라 풀이를 해보자
먼저 방문 체크를 위한 N개의 배열을 만들어준다.
val visited = BooleanArray(n)
키포인트 2번과 3번에 따라 N개의 Array만큼 반복하며, 지나가지 않은 부분을 체크해준다.
fun solution(n: Int, computers: Array<IntArray>): Int {
val visited = BooleanArray(n)
var count = 0
computers.forEachIndexed { i, _ ->
// 깊이 만큼 반복
if (!visited[i]) {
// 네트워크가 연결되었는지 체크 후, DFS 체크
dfs(i, computers, visited)
count++
}
}
return count 키포인트 4번에 따라 지나가지 않은 부분을 찾아 노드끼리 만났고, 지나가진 않은 부분을 찾는다. 그 후, 더 이어진 부분있는지 탐색할 필요가 있기 때문에 해당 함수를 한번더 반복해준다.
fun dfs(current: Int, computers: Array<IntArray>, visited: BooleanArray) {
visited[current] = true // 방문 체크
computers[current].forEachIndexed { i, isConnected ->
if (isConnected == 1 && !visited[i]) {
// 노드끼리 만났고, 방문하지 않았으면 추가로 해당 깊이 생성
dfs(i, computers, visited)
}
}
}최종 코드
fun main() {
print(
Solution().solution(
3, arrayOf(
intArrayOf(1, 1, 0),
intArrayOf(1, 1, 0),
intArrayOf(0, 0, 1)
)
)
)
}
class Solution {
fun solution(n: Int, computers: Array<IntArray>): Int {
val visited = BooleanArray(n)
var count = 0
computers.forEachIndexed { i, _ ->
// 깊이 만큼 반복
if (!visited[i]) {
// 네트워크가 연결되었는지 체크 후, DFS 체크
dfs(i, computers, visited)
count++
}
}
return count
}
fun dfs(current: Int, computers: Array<IntArray>, visited: BooleanArray) {
visited[current] = true // 방문 체크
computers[current].forEachIndexed { i, isConnected ->
if (isConnected == 1 && !visited[i]) {
// 노드끼리 만났고, 방문하지 않았으면 추가로 해당 깊이 생성
dfs(i, computers, visited)
}
}
}
}GPT의 풀이
class Solution {
fun solution(n: Int, computers: Array<IntArray>): Int {
val visited = BooleanArray(n) // 각 컴퓨터가 방문됐는지 여부를 저장할 배열
var networkCount = 0 // 네트워크(연결된 컴퓨터 집합)의 개수
// DFS 함수 정의: 현재 컴퓨터에서 연결된 모든 컴퓨터를 재귀적으로 탐색
fun dfs(current: Int) {
visited[current] = true // 현재 노드를 방문했다고 표시
// 현재 컴퓨터와 연결된 다른 컴퓨터들을 검사
for (next in 0 until n) {
// 연결되어 있고, 아직 방문하지 않은 컴퓨터라면 DFS로 탐색
if (computers[current][next] == 1 && !visited[next]) {
dfs(next)
}
}
}
// 모든 컴퓨터에 대해 방문 여부 확인
for (i in 0 until n) {
// 아직 방문하지 않은 컴퓨터는 새로운 네트워크의 시작점
if (!visited[i]) {
dfs(i) // 해당 컴퓨터에서 연결된 네트워크 전체를 방문 처리
networkCount++ // 네트워크 하나 증가
}
}
return networkCount
}
}문제를 풀며
꽤나 어려울 수 있는 2차원 배열이였음에도 노드에 대한 접근 방법에 대해 코드로 녹여낼 수 있는 생각을 얻게 된 것 같아 좋았습니다.
이번문제는 이미 지나간 중복된 네트워크를 어떻게 찾느냐가 중요했던 것 같습니다.
시간복잡도를 줄이는 최적의 방법
2차원 행렬에서 1차원과 노드로 치환 할 수 있는 방법이다.
행렬을 리스트로 치환해, index를 x로, 값을 y로 치환하여 방법을 찾게 된다.
// 메인 함수: 네트워크 개수 계산
fun solution(n: Int, computers: Array<IntArray>): Int {
val adjList = toAdjList(computers)
val visited = BooleanArray(n)
var count = 0
for (i in 0 until n) {
if (!visited[i]) {
dfs(i, visited, adjList)
count++
}
}
return count
}
// 인접 행렬 -> 인접 리스트로 변환
private fun toAdjList(computers: Array<IntArray>): List<MutableList<Int>> {
val n = computers.size
val adjList = List(n) { mutableListOf<Int>() }
for (i in 0 until n) {
for (j in 0 until n) {
if (i != j && computers[i][j] == 1) {
adjList[i].add(j)
}
}
}
return adjList
}
// DFS 탐색
private fun dfs(current: Int, visited: BooleanArray, adjList: List<List<Int>>) {
visited[current] = true
for (next in adjList[current]) {
if (!visited[next]) {
dfs(next, visited, adjList)
}
}
}