백준 1325 효율적인 해킹(dfs, bfs)

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

1325번: 효율적인 해킹

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

using namespace std;
const int MAX = 10000 + 1;
int N, M;
vector<int> graph[MAX];
bool visited[MAX];
int cnt;
int result;
vector<int> ans;

void dfs(int x)
{
    visited[x] = true;

    for (int j = 0; j < graph[x].size(); j++)
    {
        if (!visited[graph[x][j]])
        {
            cnt++;
            dfs(graph[x][j]);
        }
    }
}

void bfs(int x)
{
    visited[x] = true;
    queue<int> q;
    q.push(x);
    while (!q.empty())
    {
        int next = q.front();
        q.pop();
        for (int i = 0; i < graph[next].size(); i++)
        {
            if (!visited[graph[next][i]])
            {
                visited[graph[next][i]] = true; //bfs 문제 풀 때 자꾸 이 부분 빼먹는데 그러면 안돼!!!
                cnt++;
                q.push(graph[next][i]); //bfs는 제귀나 스택이 아닌 큐로 푼다는것 좀 기억해!!!!
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int node1, node2;
        cin >> node2 >> node1;
        graph[node1].push_back(node2);
    }
    for (int i = 1; i <= N; i++)
    {
        if (graph[i].size() != 0)
        {
            //dfs(i);
            bfs(i);
            if (cnt == result)
                ans.push_back(i);
            else if (cnt > result)
            {
                result = cnt;
                ans.clear();
                ans.push_back(i);
            }
            cnt = 0;
            for (int j = 0; j <= N; j++)
            {
                visited[j] = false;
            }
        }
    }
    sort(ans.begin(), ans.end());

    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
}

dfs와 bfs 두 버전으로 풀어봤다.

 

dfs는 꾸준히 푸는데 bfs는 연습을 안하다보니까 자꾸 이상한 곳에서 실수를 한다.

 

bfs를 풀 때 가장 주의해야하는 것은

 

visited=true 부분을 while문 안에도 하나 넣어줘야 한다는 것!

bfs는 queue를 활용한 것이기 때문에 stack이나 재귀로 표현하면 안된다!!

 

(실제로 bfs 구현을 까먹고 bfs처럼 구현하다가 queue에 넣지 않고 재귀를 시켜버리는 오류를 범했다. 이 오류를 범하게 되면 시간초과 혹은 메모리 초과와 같은 에러가 나오게 되어 있다.)