[C++] 프로그래머스 전력망을 둘로 나누기

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

1. 서론

 

처음에 뭔가 그림과 문제가 복잡해 보여서 압도됐는데 생각보다 푸는 방법이 어렵진 않았던 문제. dfs 문제다.

 

2. 문제 풀이

 

wires라는 2차원 배열이 주어진다. n개의 송전탑이 몇 번 과 몇 번이 연결되어 있는지 알려주는 배열이다. 이때 이 연결된 선들 중 한 개를 끊었을 때 양쪽 송전탑의 개수가 최대한 비슷하도록 만들었다고 가정했을 때 그 양쪽 송전탑의 차를 구하는 문제이다.

 

어떤 선을 끊는게 양쪽 송전탑의 수를 비슷하게 만드는 건지 알 수 없기 때문에 wires 배열에 주어진 선을 한 개씩 빼고 트리를 만들었다. 그리고 그 트리를 dfs로 1번부터 n번까지 방문하면서 이어지지 않은 양쪽의 송전탑 수를 구해 차를 저장해줬다. 그리고 그 차가 가장 적은 것을 답으로 return 했다.

 

발상 자체는 간단했는데 코드가 조금 복잡해졌다. 선을 한 번 씩 빼고 트리를 wires배열의 개수만큼 만들어야 하고, 만들었을 때마다 1번부터 n번까지 dfs를 돌려야 하고, 매번 그 차의 값을 구하는 것. 짜다 보니 이렇게 해야 한다는 걸 알게 됐다. (물론 다른 풀이 방법들이 있겠지만)

 

3. 코드 설명

 

#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int visit[101];
vector<int> arr[101];
int cnt = 0;

void dfs(int start)
{
    if(visit[start]) return;
    
    visit[start] = true;
    cnt++;
    
    for (int i = 0; i < arr[start].size(); i++)
    {
        int x = arr[start][i];
        dfs(x);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int i, j, x = 0, a = 0, b = 0;
    vector<int> v;
    
    for (j = 0; j < wires.size(); j++)
    {
        memset(visit, 0, sizeof(visit));
        memset(arr, 0, sizeof(arr));
        
        for (i = 0; i < wires.size(); i++)
        {
            if (x != i)
            {
                arr[wires[i][0]].push_back(wires[i][1]);
                arr[wires[i][1]].push_back(wires[i][0]);
            }
        }
        
        dfs(1);
        a = cnt;
        cnt = 0;
        
        for (i = 2; i <= n; i++)
        {
            memset(visit, 0, sizeof(visit));
            dfs(i);
            if (cnt != a)
            {
                b = cnt;
                break;
            }
            if (i == n) b = cnt;
            cnt = 0;
        }
    
        a -= b;
        if (a < 0) a *= -1;
        v.push_back(a);
        
        cnt = 0, x++;
    }
    
    sort(v.begin(), v.end());
    
    return v[0];
}

 

dfs 함수 자체는 간단하다. 방문했으면 return, 아니면 방문했다고 표시하고 송전탑의 개수를 새기 위해 cnt하기. 그리고 연결된 다음 송전탑으로 이동하며 재귀한다.

솔루션 함수에서는 v에 전선이 하나씩 빠진 케이스당 양쪽 송전탑의 차를 저장한다.

케이스를 새로 만들 때마다 매번 visit, arr배열을 재활용해야 했기 때문에 값이 누적되지 않게 메모리를 비워줬다.

memset함수도 오랜만에 써서 헤더를 까먹었는데 cstring이다.

그리고 반복문을 돌면서 전선 하나가 빠진 상태의 트리를 만들어주고 양쪽 트리의 차를 구하기 위해 1번을 방문했을 때를 기준으로 해서 n번을 방문할 때 송전탑의 수가 차이 나면 그 값을 b, 원래의 값을 a로 해서 a - b로 차를 구했다.

그리고 마지막까지 돌았는데 값이 변하지 않으면 양쪽의 송전탑 갯수가 같은 걸로 간주하고 b에 cnt 값을 넣어줬다.

나는 이부분 때문에 뭔가 히든 케이스가 뜰 줄 알았는데(트리가 두 개로 양분되는 게 아닌 케이스도 있을 것 같아서) 다행스럽게도 모든 케이스가 트리가 양쪽으로 나뉘는 모양인지라 잘 넘어갔다.