[프로그래머스] 위클리 챌린지, 전력망을 둘로 나누기 in Kotlin

참고블로그: Y_LINE's_Repository
문제보러 가기

파이썬 풀이에서 저의 아이디어를 말씀드렸습니다. 그 아이디로 Kotlin으로 언어만 바꿔서 풀어보려고 했는데, 잘 안 되네요..ㅠㅠ 그래서 블로그를 참고했습니다. Kotlin 언어로 알고리즘 풀이를 사용하는 사람들이 많이 없다고 느꼈어요. 그래도 어쩔 수 없습니다. 익숙해지려면 사용해야지요.

파이썬과 비슷한 풀이면서 좀 다르다고 느낀게 이 풀이에서는 방문한 노드를 모두 HashSet에 넣어주어 중복을 방지했다는 거에요. if(hs.contains(arr[now][i])) continue은 방문한 노드인지를 체크하는 곳인데, 노드의 갯수가 100까지라고 했으니, 시간 복잡도는 그리 크지는 않을거라고 생각합니다. 하지만, 최대한 방문 리스트나 배열을 만들어서 코드를 짜는게 제일 좋을거 같았습니다. 나중에 그렇게 한 번 다시 풀어볼 생각이에요.

1. 답을 낼 answer에는 일단 n을 할당합니다. 그 어떤 테스트케이스도 n보다 크거나 작을 수 밖에 없기 때문이죠
2. 트리의 형태이며 전력망을 배열을 만들어 줍니다.
   • 이때 중요한건 전력망이 얼마나 클지 모르기 때문에 Array<MutableLIst>로 배열 안의 원소인 리스트가 변할 수 있게 조절해줍니다.
   • 물론 이 원소의 자료형태는 모두 MutableLIst이고 개수는 n개이겠죠
3. 그리고 wires를 활용하여 트리 노드를 만들어 줍니다.
4. 이후에는 bfs 함수를 만들어 queue를 돌릴거에요.
   • hs라는 HashSet을 만들어줍니다. (여기에 방문한 노드는 집어넣어줄거에요.)
   • queue도 만들어줍시다. queue의 경우 ArrayList가 아닌 LinkedList로 만들어 주는게 시간복잡도 측면에서 좋다고 합니다.
5. 끝노드가 아닌 경우라면 해당 다른 곳은 모두 이어진 부분이니 hs에 넣어줍니다. 물론 q에도 넣어줘요.
6. 이후 queue를 돌면서 방문한(hs에 있는 노드이면) continue를 하고 그렇지 않으면 다시 hs에 넣어줍시다.
7. 양쪽 방향을 bfs함수를 활용해 양쪽 방향을 모두 돌아봅시다.
8. 이후 가장 차이가 적은 것을 업데이트 시키면 됩니다.

import java.util.Queue
import java.util.LinkedList
class Solution {
    fun solution(n: Int, wires: Array<IntArray>): Int {
        var answer = n
        val arr = Array<MutableList<Int>>(n){mutableListOf()}

        wires.forEach{
            arr[it[0] - 1].add(it[1] - 1)
            arr[it[1] - 1].add(it[0] - 1)
        }

        wires.forEach{
            answer = Math.min(answer,
                Math.abs(bfs(arr, arr[it[0]-1], it[0]-1, it[1]-1) -
                        bfs(arr, arr[it[1]-1], it[1]-1, it[0]-1)))
        }
        return answer
    }
    fun bfs(arr:Array<MutableList<Int>>, startNode:MutableList<Int>, s:Int, e:Int):Int{
        val hs = HashSet<Int>()
        val q:Queue<Int> = LinkedList<Int>()
        hs.add(s)

        for(n in startNode){
            if(n == e) continue
            hs.add(n)
            q.offer(n)
        }

        while(q.isNotEmpty()) {
            val now = q.poll()
            for(i in arr[now].indices){
                if(hs.contains(arr[now][i])) continue
                hs.add(arr[now][i])
                q.offer(arr[now][i])
            }
        }
        return hs.size
    }
}