[Algorithm]Baekjoon 2458번 : 제출

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

2458번: 키 순서

int n, m, a, b, answer;
 
vector<vector<int>> graphs[2];
int counts[2] = { 0 };
bool visited[501] = { false };
 
void DFS(int node, int flag)
{
    for (int i = 0; i < graphs[flag][node].size(); ++i)
    {
        int nextNode = graphs[flag][node][i];
 
        if (visited[nextNode]) continue;
 
        ++counts[flag];
        visited[nextNode] = true;
        DFS(nextNode, flag);
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    graphs[0].resize(501);
    graphs[1].resize(501);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
 
        graphs[0][a].push_back(b);
        graphs[1][b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        memset(visited, false, sizeof(visited));
        DFS(i, 0);
 
        memset(visited, false, sizeof(visited));
        DFS(i, 1);
 
        if (counts[0] + counts[1] == n - 1) ++answer;
        counts[0] = counts[1] = 0;
    }
 
    cout << answer;
}

프로그래머스에 있는 '순위' 라는 문제랑 완벽히 같은 문제이다.

플로이드와샬로 푸는 경우가 좀 더 대중적?인거같긴한데 나는 그때도 이렇게 풀기도했고 지금도 이 풀이가 먼저 떠오르긴 했다. 플로이드는 n^3이라서 사실 위의 dfs풀이가 더 빠르긴하다.

 

사실 코드를 더 최적화하려다가 시간만 날리고 다시 원래풀이로 풀었다.. 순위풀었을 때보다는 더 깔끔하다.