프로그래머스 Level 2 전력망 자르기 - BFS

전력망 자르기

출처 : 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

이 포스트는 광고 게시가 없는 비상업적, 비영리적 포스트임을 알려드립니다.

 

풀이

제 개인적인 의견으로 이 문제는 bfs를 연습하기 좋은 문제가 아닌가 싶습니다.

전력망이 아래와 같이 예시로 들어옵니다.

wires 첫 번째를 볼까요??

 

첫 번째 예시의 노드 그래프입니다.

문제는 어떤 한 정점에서 다른 정점으로 갈 때 중간을 자른다고 합니다.

그리고 잘린 2 부분이 개수가 가능한 비슷하도록 = 가장 작은 차이를 가지게 잘라라

라고 말하고 있습니다.

그렇다면 어떻게 자르고 어떻게 개수를 세어야 할까 이게 중요해 보이네요.

자 다시 첫 번째 예시를 보면 연결된 노드들의 집합들이 있습니다.

어떻게 잘라야 하고 어떻게 세어야 할까 가 문제 풀이의 key입니다.

아래에서 무언가 보이시나요??

저는 전선 정보를 보니 0번째 원소에 1-3 연결이 되어있으므로 

1번과 2번을 자르겠다

2번과 3번을 자르겠다

3번과 4번을 자르겠다

이렇게 표현이 되겠구나 싶었습니다.

이렇게 자르면 전선 정보를 0부터 순회하면서 연결된 전선의 자르는 경우가 모두 나오더라고요.

 

전체 노드는 최대 100개 이하입니다.  다른 방식도 분명히 있겠지만

100개 이하이므로 충분히 완전 탐색을 사용해도 되겠구나 싶었고 잘 보시면 완전탐색 항목이라고 문제에 떡하니 적혀있어서 힌트를 얻었습니다ㅋ

 

그럼 완전 탐색에 무엇을 풀어야 개수를 세어줄 수 있을까요??

여기서 잘린 두 개의 전력망이 각 각 몇 개로, 얼마나 많이 연결되어 있냐~ 를 묻고 있습니다.

네 BFS가 맛있어 보입니다. DFS도 상관없습니다.

 

이제 BFS를 이용해 풀어보겠습니다.

 

1. 먼저 BFS를 위해 각 노드가 갈 수 있는 정점을 그래프 혹은 리스트로 만들어줍니다.2. 전선 정보를 순회하면서 하나씩 잘라갑니다.3. 자른 전선 0번째와 1번째를 시작으로 각각 bfs를 돌립니다.4. 결과의 차이가 가장 작은 값을 answer로 저장합니다.

 

아래에 코드가 있습니다.

 

class Solution {
    fun solution(n: Int, wires: Array<IntArray>): Int {
        var answer: Int = Int.MAX_VALUE
        val tree = Array(n + 1) {
            mutableListOf<Int>()
        }
        wires.forEach { wire ->
            val node1 = wire[0] // 1
            val node2 = wire[1] // 3
            tree[node1].add(node2)
            tree[node2].add(node1)
        }
        wires.forEach { wire ->
            val network1 = bfs(wire[0], wire[1], tree, BooleanArray(n + 1))
            val network2 = bfs(wire[1], wire[0], tree, BooleanArray(n + 1))
            answer = min((network1-network2).absoluteValue , answer)
        }
        return answer
    }

    fun bfs(node1: Int, node2: Int, tree: Array<MutableList<Int>>, visited: BooleanArray): Int {
        var count = 1
        val queue = ArrayDeque<Int>()
        visited[node1] = true
        queue.add(node1)
        while (queue.isNotEmpty()) {
            val current = queue.removeFirst()
            tree[current].forEach { next ->
                if (!visited[next] && next != node2) {
                    count++
                    visited[next] = true
                    queue.add(next)
                }
            }
        }
        return count
    }
}

 

코드를 하나씩 살펴보겠습니다

먼저 wires 정보를 보고 정점의 정보를 리스트로 만들어줍니다.

 

이제 wires를 순회하며 하나씩 잘라보는데

network1은 wire [0]에서 시작해서 1번은 거르고 갈 수 있는 tree의 정보를 가지고 옵니다.

network2는 wire [1]에서 시작해서 0번은 거르고 갈 수 있는 tree의 정보를 가지고 옵니다.

 

bfs를 들어가면 wire [0]를 시작 정점으로 갈 수 있는 노드를 파악합니다.

가면서 방문한 적이 없고 next 노드가 node2가 아니면 갈 수 있으므로 queue에 넣어줍니다. visited도 true 합니다.

이때 count++해서 갈 수 있는 곳만 개수를 세어 방문이 다 끝나면 count를 반환합니다.

 

answer는 네트워크 1과 2에서 받아온 count의 개수를 뺀 값을 answer값과 비교해 최솟값이 무엇인지 갱신합니다.

answer = min((network1-network2).absoluteValue , answer)

 

이상으로 bfs를 이용한 전력망 자르기 문제였습니다.

다른 코드도 도움이 되리라 생각합니다. 함께 보면서 공부하시면 더 넓은 시야를 가질 거라고 봅니다. 저 또한 마찬가지고요. 읽어주셔서 감사합니다.