solved.ac CLASS 3 백준 1389

기본적인 BFS 문제였다.

처음에 BFS 로 구현해서 바로 제출을 했는데 틀렸다.

처음에 depth 라는 변수를 두고 그 while 문 들어가는 곳에 depth ++ 로 BFS 의 깊이를 측정하려 했다.

그렇게 되면 depth 가 증가하기만 하고 q 에서 pop 되는 지점으로 depth 를 돌려야 하는데 그렇게 하지 못했다. 아래 소스는 내가 틀렸던 소스이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int M, N, A, B;
int friendArr[102][102];
int check[102];
int kbArr[102];

int BFS(int start, int friendNum){

    queue<int> q;
    check[start] = 1;
    q.push(start);
    int depth = 0;
    while (!q.empty()) {
        depth ++;
        int x = q.front(); q.pop();
        for (int i = 1; i <= friendNum; i++) {
            if(friendArr[x][i] == 1 && check[i] == 0){
                check[i] = depth;
                q.push(i);
            }
        }
    }
    int KBGNum = 0;
    for (int i = 0; i < friendNum; i++) {
        KBGNum += check[i+1];
    }
    memset(check, 0, sizeof(int) * friendNum);
    return KBGNum;
}

int main(void){
    
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        friendArr[A][B] = 1; friendArr[B][A] = 1;
    }
    int MIN = 987654321; int minIdx = 0;
    for (int i = 1; i <= N; i++) {
        kbArr[i] = BFS(i, N);
        if(kbArr[i] < MIN){
            MIN = kbArr[i];
            minIdx = i;
        }
    }
    
    cout << minIdx << '\n';
    
    return 0;
}

 

여기서 애초에 depth 를 두고 풀면 안되었다. 위에서 설명 했듯이 BFS 에서 depth 의 개념은 q 에 의존한다. 따라서 q 의 상태를 저장하거나 check 배열에 방문을 안했을 때를 -1 로 두고 방문했을 때 그 길이를 저장해서 이 문제를 해결하였다. 아래 소스는 정답 소스이다

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int M, N, A, B;
int friendArr[102][102];
int kbArr[102];
int check[102];

int BFS(int start, int friendNum){
    
    memset(check, -1, sizeof(int)*(friendNum + 1));
    queue<int> q;
    check[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = 1; i <= friendNum; i++) {
            if(friendArr[x][i] == 1 && check[i] == -1){
                check[i] = check[x] + 1;
                q.push(i);
            }
        }
    }
    int KBGNum = 0;
    for (int i = 1; i <= friendNum; i++) {
        KBGNum += check[i];
    }
    memset(check, 0, sizeof(int) * friendNum);
    return KBGNum;
    
}

int main(void){
    
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        friendArr[A][B] = 1; friendArr[B][A] = 1;
    }
    int MIN = 987654321; int minIdx = 0;
    for (int i = 1; i <= N; i++) {
        kbArr[i] = BFS(i, N);
        if(kbArr[i] < MIN){
            MIN = kbArr[i];
            minIdx = i;
        }
    }
    
    cout << minIdx << '\n';
    
    return 0;
}