백준 1058 - 친구 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/1058

풀이전략

1. 서로간에 거리가 2인 값들을 찾는 문제이다.

코드

#include<bits/stdc++.h>
// 문제파악을 잘못함 ... 
using namespace std;

int N;
int cnt = 0;
int res = 0;
vector<int> a[51];
bool ch[51];

void DFS(int L,int v){
    
    ch[v] = true;
    if(L == 2) return ;
    
    for(int i=0; i<a[v].size(); i++){
        DFS(L+1, a[v][i]);   
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    char tmp;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> tmp;
            if(tmp == 'Y') a[i].push_back(j);
        }
    }

    for(int i=1; i<=N; i++){
        memset(ch, false, sizeof(ch));
        cnt = 0;
        DFS(0,i);
        for(int i=1; i<=N; i++){
            if(ch[i] == true) cnt++;
        }
        res = max(res, cnt);
    }
    
    cout<<res-1<<endl;
    

    return 0;
}

소감

처음에는 연결된 친구들 모두를 찾는 문제라고 생각했지만 결국 서로간의 거리가 2인 값들을 찾는 문제이다. 문제를 제대로 파악하는것이 중요하다. 또한 플로이드와샬, 냅색, 다익스트라 등의 알고리즘 공부가 시급하다.