백준 1058 친구 C++

https://www.acmicpc.net/problem/1058

1058번: 친구

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1058_bfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ1058 친구
//
//  Created by Hwayeon on 2021/08/26.
//

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int max_friends = 0;
int N;
char relationship[50][50] = {'N'};
int visit[50] = {0, };

void bfs(int v){
    memset(visit, 0, sizeof(visit));
    queue<pair<int,int>> q;
    q.push({v, 0});
    visit[v] = 1;
    int friends = 0;
    int depth = 0;
    while(!q.empty()){
        int now_v = q.front().first;
        int depth = q.front().second;
        q.pop();
        if(depth > 1) continue;
        for(int i=0; i<N; i++){
            if(relationship[now_v][i] == 'Y' && visit[i] == 0){
                visit[i] = 1;
                friends++;
                q.push({i, depth+1});
            }
        }
    }
    if(friends > max_friends) max_friends = friends;
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> relationship[i][j];
        }
    }
    for(int i=0; i<N; i++){
        bfs(i);
    }
    cout << max_friends << endl;
    return 0;
}

---

풀이 과정

 친구 관계를 나타내는 입력이 N*N으로 주어진다. 즉, 인접 행렬 방식으로 그래프의 연결 관계를 표현한 입력이 주어진다는 것을 알 수 있다.

이 문제의 핵심은 A의 2-친구는 결국 A와 거리 2이내에 연결되어 있는 노드의 수라는 것이다.

이를 고려해서 각 노드별로 최대 깊이가 2인 노드까지만 방문하면서 친구 수를 카운팅 해주면 된다. BFS와 DFS 알고리즘을 활용할 수 있다는 것을 짐작할 수 있다.

하지만 실제로 두 가지 모두 적용해보니 DFS 방법으로는 풀 수 없는 경우가 있었다.(이에 대해서는 아래에 설명하도록 하겠다.)

 

 따라서 BFS 알고리즘을 활용하여 문제를 해결했고 코드는 다음과 같다.

풀이 시간 37분

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int max_friends = 0;
int N;
//입력에 주어지는 친구 관계를 담는 배열
char relationship[50][50] = {'N'};
//이전에 카운팅한 친구를 재 탐색하지 않도록 방문 처리를 하기 위한 배열
int visit[50] = {0, };

void bfs(int v){
	//사람 v의 친구 수를 체크하기 위해 visit 배열을 초기화
    memset(visit, 0, sizeof(visit));
    
    //{친구, v와의 관계 깊이}
    //v와의 관계 깊이 = 시작 노드와의 거리, 2 이하이어야 2-친구이다
    queue<pair<int,int>> q;
    
    //BFS 탐색을 시작하기 위해 시작 노드는 v, 관계 깊이는 0, visit[시작 노드] = 1로 셋팅한다
    q.push({v, 0});
    visit[v] = 1;
    
    //사람 v의 친구 수
    int friends = 0;
    while(!q.empty()){
        int now_v = q.front().first;
        int depth = q.front().second;
        q.pop();
        //depth가 2 이상이라면 더이상 탐색하지 않는다
        if(depth > 1) continue;
       	//친구 탐색
        for(int i=0; i<N; i++){
        	//현재 노드 now_v에 연결되어 있는 노드이면서 이전에 방문하지 않은 노드인 경우, friends를 카운팅
            if(relationship[now_v][i] == 'Y' && visit[i] == 0){
                visit[i] = 1;
                friends++;
                q.push({i, depth+1});
            }
        }
    }
    //사람 v의 친구수가 이전 사람들의 친구수보다 많은 경우, max_friends를 갱신한다
    if(friends > max_friends) max_friends = friends;
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> relationship[i][j];
        }
    }
    //각 사람별 친구 수를 구한다
    for(int i=0; i<N; i++){
        bfs(i);
    }
    cout << max_friends << endl;
    return 0;
}
//시간복잡도 = O(V(V+E)) = O(V^2), 공간복잡도 = O(V^2)

---

오답 노트

결론: 예외 상황이 발생하므로 DFS를 적용할 수 없다.

 BFS로 문제를 해결한 후 DFS로도 문제를 풀어보기 위해 DFS를 적용한 코드를 짜봤다.

#include <iostream>
#include <string.h>
using namespace std;

int N;
char relationship[50][50] = {'N',};
int max_friends = 0;
int visit[50] = {0,};
int friends = 0;

void dfs(int v, int depth){
	//현재 친구수가 max_friends보다 많다면 max_friends를 갱신한다
    if(friends > max_friends) max_friends = friends;
    
    //시작 노드로부터 거리가 2 이상인 경우, 더 이상 탐색하지 않는다
    if(depth > 1) return;
    
    //친구 탐색
    for(int i=0; i<N; i++){
    	//이전에 방문하지 않았고 노드 v와 연결되어 있는 경우, 친구수를 카운팅 한다
        if(visit[i] == 0 && relationship[v][i] == 'Y'){
            visit[i] = 1;
            friends++;
            dfs(i, depth+1);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> relationship[i][j];
        }
    }
    //각 사람에 대하여 친구 수를 구한다
    for(int i=0; i<N; i++){
    	//visit 함수 초기화
        memset(visit, 0, sizeof(visit));
        //친구수 0으로 초기화, 현재 시작 노드 방문 처리
        friends = 0;
        visit[i] = 1;
        dfs(i, 0);
    }
    cout << max_friends << endl;
    return 0;
}

코드를 짜면서는 무난히 통과할 것이라고 생각했다. 하지만 다음과 같은 테스트케이스 같은 경우, 정답을 출력하지 못한다.

 

• 테스트 케이스

6

 

NYYNYN

YNYNNN

YYNYNN

NNYNNN

YNNNNY

NNNNYN

 

• 출력

 

 실제로 그래프를 그려보면 0번의 친구는 0 -> 1 -> 2 -> 3-> 4-> 5로 탐색되어야 하는데, 위의 출력 결과를 보면 3은 탐색이 이뤄지지 않는다.

그 이유는 당연하다!

0 -> 1 -> 2 까지 탐색하면 현재 visit = [1, 1, 1, 0, 0, 0]이고, dfs(2, 2) 호출에서 depth가 2이기 때문에 더 탐색이 이뤄지지 않고 끝난다.

그러면 그다음 4->5를 방문하고 0번의 친구는 총 4명으로 출력이 될 것이다.

즉, 2번 친구를 1번의 친구로 탐색을 했기 때문에 방문처리가 되어서, 0 -> 2 -> 3의 경우를 탐색하지 못하는 것이다.

따라서 이와 같은 예외에 있어서 탐색이 이뤄지지 않을 노드가 발생하기 때문에, BFS 알고리즘을 활용하는 것이 적절하다.