[프로그래머스/Kotlin]Lv3 - 네트워크

프로그래머스

문제

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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개의 네트워크가 있습니다.

풀이

나의 풀이

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        var changeCnt = 0
        var network: Array<Int> = Array(n) { 0 }

        for (i in 0 until n) {
            for (j in 0 until n) {
                if (computers[i][j] == 1) {
                    if (network[i] != 0 && network[j] != 0) {
                        if (i==j) continue
                        if (network[i] != network[j]) {
                            val min = minOf(network[i], network[j])
                            val max = maxOf(network[i], network[j])
                            network = network.map { if (it==max) min else it }.toTypedArray()
                            changeCnt++
                        }
                    } else if (network[i] == 0 && network[j] == 0) {
                        answer++
                        network[i] = answer
                        network[j] = answer
                    }
                    else if (network[i] != 0) network[j] = network[i]
                    else if (network[j] != 0) network[i] = network[j]
                }
            }
        }

        return answer + network.filter { it==0 }.size - changeCnt
    }
}

1. i와 j는 연결되어있을 때, i와 j가 모두 네트워크 번호를가지고 있다면 

  - i와 j가 같은 경우 continue

  - i와 j의 네트워크번호가 다른 경우, 작은 번호로 replace (map 사용)

  - 새로운 네트워크에서 기존 네트워크로 변경되므로 changeCnt에 추가

2. i와 j는 연결되어있을 때, i의 네트워크 번호와 j의 네트워크 번호가 없다면

  - 새로운 네트워크가 생성된 것이므로 answer의 값을 +1

  - i와 j에 answer에 해당하는 네트워크 번호 추가

3. i가 네트워크 번호를 가지고 있으면 j의 네트워크 번호는 i와 동일하게 변경

4. j가 네트워크 번호를 가지고있으면 i의 네트워크 번호는 j와 동일하게 변경

5. answer 값과 네트워크 번호가 없는 번호의 개수를 더하고 changeCnt를 뺀 값을 리턴

  - answer는 만들어진 네트워크 개수

  - 네트워크 값이 없는 번호들은 모두 개별 네트워크로 생성됨

  - changeCnt는 만들어진 네트워크 중 무효 처리된 네트워크의 개수

Comment

원래의 정석 풀이라면 dfs로 풀었을 것이다.

나도 처음 이 문제를 접하고 당연히 dfs로 풀려고 했다.

그런데 하... 진짜 너무 귀찮았다 ㅋㅋㅋㅋ visited 잡고 dfs 재귀 돌리는거... 생각하는게 너무 귀찮았다

그래서 그냥 조건문 걸고 이중 for문으로 끝내버렸다.

그 과정에서 조건이 너무 복잡해져서 중간에 그냥 간단하게 dfs로 만들걸 후회하긴 했으나

오기로 끝까지 저 방법으로 끝내버렸다.

비교적 간단한 문제였다.