[백준] 2485번 키 순서 (C)

출처

한국정보올림피아드 지역본선 2011 초등부 4번

문제 번호

백준 2458번 키 순서
코드업 4714 : 키 순서

알고리즘

DFS

힌트

• 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음
• 나보다 큰 아이보다 큰 아이는 나보다 큼
• 나보다 작은 아이보다 작은 아이는 나보다 작음
• 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음

 

풀이

들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색할건지 d를 인자로 받는다.

여기서 check배열이 필요 없다고 생각할 수 있는데 a < b b < c b < d c < d 로 입력이 들어오는 경우 a에 대해 탐색을 할 때 a - b - c - d - d로 d를 두번 확인하게 된다.

#include<iostream>
using namespace std;
int n,m;
int graph[501][501];
int check[501];

int dfs(int a, int d){
    int sum=0;
    for(int i=1;i<=n;i++){
        if(graph[a][i]==d&&!check[i]){
            sum++;
            check[i]=1;
            sum+=dfs(i,d);
        }
    }
    return sum;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a][b]=1; // 작 
        graph[b][a]=2; // 크 
    }

    int ans=0;

    for(int i=1;i<=n;i++){

        if(dfs(i,1)+dfs(i,2)==n-1){
            ans++;
        }

        for(int j=1;j<=n;j++)
            check[j]=0;    
    }
    cout<<ans;
}

백준 2456번 키 순서 정확한 풀이

코드업 4714 : 키 순서 정확한 풀이