프로그래머스 월간코드챌린지 전력망을 둘로 나누기

간단한 문제지만 ide를 안쓰니 조금 불편했던 문제..

선 하나를 끊은 뒤에 둘로 나눠서 서로 노드의 개수가 최소가 되도록 하면 되는 문제이다

문제

문제 풀이

1. 2차원 벡터 값을 따로 graph형태로 입력 받는다 .
2. 입력받은 값들을 순회하면서 하나하나씩 끊은 뒤 bfs 돌린후 노드 차이와 answer 값을 비교하면서 값을 갱신하면 끝나는 문제이다

실수

for (int i = 1; i <= n; i++) {
            if (tmp[now][i] ) {
               // int nx = tmp[now][i];
                if(visited[i]) continue;
                q.push(i);
                visited[i] = 1;
                cnt++;
            }
        }

이 부분에서 실수했다 평소 2차원 벡터로 사용하지만 ide가 없으니 불편해서 2차원 배열로 사용했다.
tmp[now][i] - > 현재 now노드랑 연결된 요수가 참이다 그럼 그 연결된 부분은 i인데 자꾸 무슨 이상한 nx를 사용하면서 무조건 값이 1이 되도록 코드를 만들었었다... 이부분은 개선하면서 바로 solve되었다..

그리고 for문을 볼때 전선들이 1번부터 n번까지 있기에 이것을 주의해야한다

소스

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <iostream>

using namespace std;

int a[101][101];
int tmp[101][101];
int cnt;
int bfs(int x, int n) {
    queue<int> q;
    q.push(x);
    bool visited[200] = {false, };
    visited[x] = 1;
    cnt = 0;
    while (!q.empty()) {
        int now = q.front(); q.pop();

        for (int i = 1; i <= n; i++) {
            if (tmp[now][i] ) {
               // int nx = tmp[now][i];
                if(visited[i]) continue;
                q.push(i);
                visited[i] = 1;
                cnt++;
            }
        }
    }
    return cnt;
}
int solution(int n, vector<vector<int>> wires) {
    int answer = 987654321;


    for (int i = 0; i < wires.size(); ++i) {
        int t1 = wires[i][0];
        int t2 = wires[i][1];
        a[t1][t2] = 1;
        a[t2][t1] = 1;
    }

    // 하나씩 끊어서 해당 끊어진 번호들과 연결된 노드 갯수 헤아리고 - 해서 결과값고 answer값 비교해서 min 
    for (int i = 0; i < wires.size(); i++) {
        memcpy(tmp, a, sizeof(a));

        int t1 = wires[i][0];
        int t2 = wires[i][1];
       // cout << t1 << " " << t2 << endl;
        tmp[t1][t2] = 0;
        tmp[t2][t1] = 0;

        int r1 = bfs(t1, n);
        int r2 = bfs(t2, n);
       //cout << r1 << " " << r2 << endl;

        answer = min(answer, abs(r1 - r2));
    }
    return answer;
}