[Lv.2] 전력망을 둘로 나누기 [프로그래머스_코딩테스트] [DFS, Greedy] [50분]

🔍 문제 요약

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

프로그래머스

송전탑 노드가 숫자들로 주어질 때 각 숫자를 연결하는 wires라는 배열이 주어진다. (ex. [[1, 2], [2, 3], [3,4]]) 이 때 연결을 하나를 잘라서 2개의 연결로 나눴을 때, 나뉘어진 노드들의 개수의 차가 제일 적은 경우의 절대값을 구하기

 

🧠 나의 접근 방식과 시행착오

사실 문제를 봤을 때 알고리즘에서 약한 DFS, BFS 문제란 걸 직감하고 틀릴 것 같긴 했지만 재귀를 쓴다는 DFS 방식을 알고 있어서 시도를 해보았다. 결과적으로는 맞는 문제도 나왔지만 틀린 케이스들이 꽤 발생을 하여서 풀었던 코드와 gpt에게 물어본 풀이 피드백을 보고 학습을 해보고자 한다. 일단 시도했던 풀이는 시작 노드에서 필터 노드라는 것들 두고 해당 노드는 지나지 않게 재귀를 타고 타고 가서 마지막 노드일 때는 1을 반환해서 count를 증가시키는 방식을 생각했다. (예제로 주어진 테스트 케이스 중에 2개는 운좋게 맞긴 했으나 하나가 틀렸을 때 틀린 부분이 있겠구나 생각을 함) 다만 문제를 푸는데 주어진 50분을 다 채워서 디버깅을 해보다가 멈추고 풀이를 보기로 함

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 전력망을 둘로 나누기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/86971
    /// </summary>
    public int solution(int n, int[,] wires)
    {
        int answer = int.MaxValue;
        int length = wires.GetLength(0);
        
        for (int i = 0; i < length; i++)
        {
            int start = wires[i, 0];
            int end = wires[i, 1];
            int calc1 = Find(start, end, wires);
            int calc2 = Find(end, start, wires);

            int calc = Math.Abs(calc1 - calc2);

            if (answer > calc)
            {
                answer = calc;
            }
        }
        
        return answer;
    }

    public int Find(int start, int filter, int[,] wires)
    {
        int count = 0;
        int length = wires.GetLength(0);

        for (int i = 0; i < length; i++)
        {
            int s = wires[i, 0];
            int e = wires[i, 1];

            if (start == s && e != filter)
            {
                count += Find(e, s, wires);
            }
            else if (start == e && s != filter)
            {
                count += Find(s, e, wires);
            }
        }

        if (count == 0) return 1;

        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        Console.WriteLine(sl.solution(9,
            new int[,] { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 7, 8 }, { 7, 9 } }));
        Console.WriteLine(sl.solution(4,
            new int[,] { { 1,2 }, {2, 3}, {3, 4} }));
        Console.WriteLine(sl.solution(7,
            new int[,] { { 1, 2 }, { 2, 7 }, { 3, 7 }, { 3, 4 }, { 4, 5 }, { 6, 7 }}));
    }
}

✅ 풀이 코드

문제를 gpt가 추천해줬을땐 DFS라고 하더니 풀이는 BFS 방식을 내놓았다. 일단 문제를 내가 접근한 방식이 틀리진 않았지만 문제가 될 수 있는 부분들이 존재한다고 함. wires 자체가 고정된 채로 놔두고 filter라는 것으로 제어를 해보려고 시도했던 점인데, 이런 경우 재귀 호출이 중복 방문이 되면서 무한 루프가 생기거나 방문 체크가 누락되면서 시간 복잡도가 올라가는 케이스가 존재. 삭제된 간선이 여전히 존재하면서 들린 곳을 또 들릴 수도 있는 것도 생긴다. 그래서 추천해준 방식이 인접리스트 + BFS (or DFS)라고 함.

풀이로 준 풀이코드를 보긴 했는데 생각보다 많이 길어져 있는 것을 알수 있다. list도 많이 쓰이는 듯 하고..

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] wires) {
        int minDiff = int.MaxValue;

        for (int cut = 0; cut < wires.GetLength(0); cut++) {
            var graph = new List<int>[n + 1];
            for (int i = 1; i <= n; i++) graph[i] = new List<int>();

            for (int i = 0; i < wires.GetLength(0); i++) {
                if (i == cut) continue; // 하나 끊기
                int a = wires[i, 0];
                int b = wires[i, 1];
                graph[a].Add(b);
                graph[b].Add(a);
            }

            int count = BFS(graph, n, wires[cut, 0]);
            int diff = Math.Abs(n - count - count);
            minDiff = Math.Min(minDiff, diff);
        }

        return minDiff;
    }

    int BFS(List<int>[] graph, int n, int start) {
        bool[] visited = new bool[n + 1];
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        visited[start] = true;
        int count = 1;

        while (queue.Count > 0) {
            int now = queue.Dequeue();
            foreach (var next in graph[now]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.Enqueue(next);
                    count++;
                }
            }
        }

        return count;
    }
}

 

추천 받아서 본 풀이는 graph라는 변수명을 쓴 거처럼 뭔가 그래프를 생각해서 풀이를 한 듯 하다. (사이클 고려한 것으로 보임) 문제에서 주어진 제한 조건이 트리 구조로 된다는 것을 알 수 있어서 이 부분을 트리로 해서 다시 풀이를 달라고 함

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] wires) {
        int minDiff = n;

        // 인접 리스트 구성
        var graph = new List<int>[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new List<int>();
        for (int i = 0; i < wires.GetLength(0); i++) {
            int a = wires[i, 0];
            int b = wires[i, 1];
            graph[a].Add(b);
            graph[b].Add(a);
        }

        // 간선 하나씩 끊기 시뮬레이션
        for (int i = 0; i < wires.GetLength(0); i++) {
            bool[] visited = new bool[n + 1];
            int a = wires[i, 0];
            int b = wires[i, 1];

            // a-b 간선을 끊는다
            int count = DFS(a, b, graph, visited);
            int diff = Math.Abs((n - count) - count);
            minDiff = Math.Min(minDiff, diff);
        }

        return minDiff;
    }

    private int DFS(int node, int block, List<int>[] graph, bool[] visited) {
        visited[node] = true;
        int count = 1;

        foreach (var next in graph[node]) {
            if (next == block || visited[next]) continue;
            count += DFS(next, block, graph, visited);
        }

        return count;
    }
}

 

추가로 diff를 구할 때 int diff = Math.Abs((n - count) - count); 와 같은 식으로 한 쪽만 계산을 하면 한 쪽을 전체 개수에서 구할 수 있다는 점은 기억해둘만할 듯 하다.

 

🔄 정리

문제의 풀이를 보고 이해를 하긴 했으나 너무 과한 풀이가 아닌가란 생각이 든 문제긴 하다. 기존의 내 풀이에서 좀 더 개선을 하면 어떻게 되지 않을까 싶기도 한 문제.