[BOJ][C++] 백준 1058번 : 친구

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

1058번: 친구

 

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

 

어림도 없는 풀이 1 

겹지인을.. 생각하지 못했다.. 예제3번만 보고.. 신나게 풀었다

예제1도 틀리는 코드를 만들었다

#include <iostream>
#include <vector>

using namespace std;

int main() {
    
    //세팅
    int n;
    cin >> n;
    vector <int> arr[n];
    int one[n], two[n];
    
    //입력
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            char tmp;
            cin >> tmp;
            if(tmp == 'Y'){
                arr[i].push_back(j);
            }
        }
    }
    
    //1-친구 수 구해서 배열에 넣기
    for(int i=0; i<n; i++){
        one[i] = arr[i].size();
    }
    
    //2-친구 수 구해서 배열에 넣기
    for(int i=0; i<n; i++){
        two[i] = one[i]; //2-친구는 본인의 1-친구 수 +
        for(int j=0; j<arr[i].size(); j++){
            two[i] += one[i] - 1; // + 본인의 1친구들의 1친구 수 -1
        }
    }
    
    //출력
    int tmp = 0;
    for(int i=0; i<n; i++){
        if(tmp < two[i])
            tmp = two[i];
    }
    cout << tmp;
    
    return 0;
}

 

어림도없는풀이 2

DFS로 풀었다.

예제는 다 풀림

근데 왜 틀렸습니다냐고

#include <iostream>
#include <algorithm>

using namespace std;

int n;  //사람 수
bool arr[51][51] = {false}; //친구관계를 나타내는 인접배열
bool visited[51]; //방문한 노드 표시하기
int ans[51] = {0}; //i번째 사람의 2-친구 수

//깊이 2까지 돌아가는 dfs
void dfs (int level, int i){
    
    visited[i] = true;
    
    if(level == 2) return;
    
    for(int j=0; j<n; j++){
        if(arr[i][j] && !visited[j]){ //인접한데 방문 안되어있으면
            dfs(level+1, j);
        }
    }
}

int main() {
    
    //입력받기
    cin >> n;
    char tmp;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> tmp;
            if(tmp == 'Y') arr[i][j] = true;
        }
    }
    
    //각 사람에서 출발해서
    for(int i=0; i<n; i++){
        
        //초기화하고
        int cnt = 0;
        for(int j=0; j<51; j++){
            visited[j] = false;
        }
        
        //깊이 2만큼 dfs 돌리고
        dfs(0,i);
        
        //방문 표시된 노드 개수 세면
        for(int j=0; j<n; j++){
            if(visited[j])
                cnt++;
        }
        
        //2-친구 수가 나옴
        ans[i] = cnt-1; //본인은 빼야함 (-1)
    }
    
    //답 배열에서 가장 큰 수 고르기
    sort(ans, ans+51);
    cout << ans[50];
    
    
    return 0;
}

https://www.acmicpc.net/board/view/44710

글 읽기 - 반례 말씀해주시면 감사하겠습니다.

나랑 같은 방법으로 푸신 분의 질의응답을 보고 알았다..

기가막히게 여기 답변자분께서 제시해주신 예제가 딱 틀리더라....

 

알고보니

방문처리가 되어버리면 bfs를 돌리다가 멈추고 있었다

 

그래서..

 

(진짜) 풀이 

방문처리 없이 인접배열을 다 돌 수 있게 벡터로 바꿨다

그리고.. 이건 BFS 도 아니고 DFS 도 아닌

뭔가 둘이 섞인

오묘한... 이상한 애가 되었다

대충 B랑 D 사이에 있는 풀이법이니

CFS 라고 하자 ㅎㅋㅎ

큐 없이 BFS 구현한 느낌..?!

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;  //사람 수
vector <int> arr[51]; //친구관계를 나타내는 인접배열
bool visited[51];   //방문여부
int ans[51] = {0}; //i번째 사람의 2-친구 수

//깊이 2까지 돌아가는 dfs
void dfs (int level, int i){
    
    visited[i] = true;
    
    if(level == 2) return;
    
    for(int j=0; j<arr[i].size(); j++){
        dfs(level+1, arr[i][j]);
    }
}

int main() {
    
    //입력받기
    cin >> n;
    char tmp;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> tmp;
            if(tmp == 'Y') arr[i].push_back(j);
        }
    }
    
    //각 사람에서 출발해서
    for(int i=0; i<n; i++){
        
        //초기화하고
        int cnt = 0;
        for(int j=0; j<51; j++){
            visited[j] = false;
        }
        
        //깊이 2만큼 dfs 돌리고
        dfs(0,i);
        
        //방문 표시된 노드 개수 세면
        for(int j=0; j<n; j++){
            if(visited[j])
                cnt++;
        }
        
        //2-친구 수가 나옴
        ans[i] = cnt-1; //본인은 빼야함 (-1)
    }
    
    //답 배열에서 가장 큰 수 고르기
    sort(ans, ans+51);
    cout << ans[50];
    
    
    return 0;
}

 

그리고...

그냥 올리는 알아볼수없는 풀이들

각자 풀이 1 2 3이다