[BaekJoon][1260] DFS와 BFS

BAEKJOON ONLINE JUDGE

1260 DFS와 BFS

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

엄청 틀려서 충격먹음!!

처음에 풀때는 가볍게 한번에 맞았는데

왜 다시 푸는데 엄청 틀렸지...

처음에는 인접행렬로 접근해서 연결된 정점의 순서가 오름차순으로 보장이 되었다.

하지만 두번 째는 인접리스트로 데이터를 표현했다.

--> 인접리스트는 입력 순서대로 넣기 때문에 순서는 보장하나 정점의 값의 정렬은 보장하지 않는다 !

그냥 인접리스트에 있는 순서대로 탐색하면 오름차순으로 탐색하는것이 아닌건 당연!

그래서 틀림

21분

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int n;
int visit[1001];
int graph[1001][1001];
 
void dfs(int num)
{
    printf("%d ", num);
    for (int i = 1; i <= n; i++)    {
        if (graph[num][i] && visit[i] == 0) {
            visit[i] = 1;
            dfs(i);
        }
    }
}
 
void bfs(int start)
{
    queue<int> que;
 
    for (int i = 0; i <= n; i++)        visit[i] = 0;
 
    que.push(start);
    visit[start] = 1;
 
    while (!que.empty()) {
        int num = que.front();
        que.pop();
 
        printf("%d ", num);
 
        for (int i = 1; i <= n; i++) {
            if (graph[num][i] && visit[i] == 0) {
                visit[i] = 1;
                que.push(i);
            }
        }
    }
 
    printf("\n");
}
 
int main()
{
    int m, start;
    int one, two;
 
    scanf("%d %d %d", &n, &m, &start);
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &one, &two);
 
        graph[one][two] = graph[two][one] = 1;
    }
 
    visit[start] = 1;
    dfs(start);
    printf("\n");
    bfs(start);
 
    return 0;
}