[Programmers] 위클리 챌린지 9 (+ 위클리 챌린지 8)

안녕하세요. 이번 포스팅에서는 위클리 챌린지 9 전력망을 둘로 나누기 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

코딩테스트 연습 - 9주차

 

위 링크에서 확인하실 수 있습니다.

 

 

위클리 챌린지 문제가 퀄리티가 좀 떨어지는 듯한 느낌을 받아서... 매주 월요일마다 안 챙겨서 풀었는데, 마침 이번 주에 네이버 코딩 테스트가 실시될 예정이어서 다시 코테 감좀 살릴 겸 풀어보았습니다.

 

해당 문제는 트리구조가 보장되기 때문에 edges 하나를 끊으면 무조건 두개의 트리로 분할될 수밖에 없습니다.

 

따라서

1. 사전의 edges 정보를 기록한 배열을 2차원으로 저장해놓은 뒤, (edges[i][j] = 1 -> i~j 연결 선 존재)

 

2. i = 1 ~ n, j = i+1 ~ n으로 순회하며, edges가 있다면, 제거하고 (edges[i][j] = 0, edges[j][i] = 0)

 

3. dfs를 두번 수행하여 각 노드에 연결된 노드가 몇 개인지 확인합니다.

 

4. 매번 결과값을 갱신해주고, 탐색이 끝났다면, edges를 원래대로 1로 바꾸어 줍니다.

 

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int edges[104][104], res = 99999999, N;
bool visited[104];
int go(int cur) {
    int ret = 1;
    for(int i = 1; i <= N; i++) {
        if(!visited[i] && edges[cur][i]) {
            visited[i] = 1;
            ret += go(i);
        }
    }
    return ret;
}
int solution(int n, vector<vector<int>> wires) {
    N = n;
    for(int i = 0; i < wires.size(); i++) 
        edges[wires[i][0]][wires[i][1]] = 1, edges[wires[i][1]][wires[i][0]] = 1;

    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            if(edges[i][j] == 0) continue; 
            vector<int> v;
            fill(visited, visited+104, false);
            
            edges[i][j] = 0;
            edges[j][i] = 0;
            
            for(int k = 1; k <= n; k++){
                if(!visited[k]) {
                    visited[k] = 1;
                    v.push_back(go(k));
                }
            } 
            res = min(res, abs(v[1] - v[0]));
            
            edges[i][j] = 1;
            edges[j][i] = 1;
        }
    }
    return res;
}

 

 

* 위클리 챌린지 8 풀이

 

위클리 챌린지 8의 경우

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

코딩테스트 연습 - 8주차_최소직사각형

 

테이블을 for문 하나로 순회하며, 

 

뒤집지 않은 경우 결과 너비 vs 뒤집은 경우 결과 너비 중 작은 값으로 매번 갱신하며 끝까지 순회하였습니다. (O(N))

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;
int res = 99999999;
void go(int idx, int width, int height, vector<vector<int>>& s) {
    if(idx == s.size()) {
        res = min(res, width*height);    
        return;    
    }
    
    int curW = s[idx][0], curH = s[idx][1];
    int a = max(curW, width), b = max(curH, height), c = max(curH, width), d = max(curW, height); 
    if(a*b >= c*d) go(idx+1, c, d, s); 
    else go(idx+1, a, b, s); 
}
int solution(vector<vector<int>> sizes) {
    int answer = 0;
    
    go(0, 0, 0, sizes);
    return res;
}