[백준/BOJ] 1260번 C++ DFS와 BFS, OutOfBounds 이유

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

1260번: DFS와 BFS

---

 백준 1260번 DFS와 BFS를 구현하는 문제다. OutOfBounds가 떴는데, 이에 대한 이유는 밑에서 설명할 예정이다.

 

  A. B. C. D. E의 우물이 있다고 가정하자. 이 우물을 파는 방법은 2가지가 있다. 첫 번째는 A 우물을 끝까지 다 판 후에 B로 넘어가서 B를 전부 파고, C, D, E도 같은 방식으로 파는 것이다.

 두 번째는 A 우물을 2m 파고, B 우물을 2m 파고, C, D, E도 같은 방식으로 파는 것이다. E를 2m 팠다면, 다시 A를 2m 파는 것처럼 동시에 5개 우물을 파는 방식이다.

 첫 번째는 DFS와 유사한 탐색방법이고, 두 번째는 BFS와 유사하다.

 

 DFS(Depth First Search)

 깊이 우선 탐색은, 루트 노드에서 시작하여 해당 분기를 모두 탐색한 후, 다음 분기로 넘어가는 탐색 방법을 의미한다. 이는 스택이나, 재귀함수를 통해 구현할 수 있다.

 

BFS(Breadth First Search)

 너비 우선 탐색은, 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미한다. 이는 큐로 구현할 수 있다.

---

1260번 테스트 케이스 이해, 해석

 해당 문제에서는 노드, 간선의 길이, 시작 노드가 주어지고, 연결된 노드가 한 줄씩 제시된다.

이를 그림으로 구현하면 위와 같다. DFS(깊이 우선 탐색)의 경우 시작 노드인 1부터 탐색을 한 뒤, 인접한 노드이면서 가장 작은 숫자인 2를 방문할 것이고, 그 다음은 2와 연결된 4를 먼저 방문할 것이다. 그 이후 1과 연결되어 있었던 3을 방문할 것이다.

BFS(너비 우선 탐색)의 경우 1 탐색 후, 인접한 2를 탐색, 그리고 인접한 3, 4를 순서대로 탐색할 것이다.

 

이 때 중요한 것은,

 테스트 케이스 2처럼, 숫자를 오름차순으로 입력하지 않는 경우를 조심해야 한다.

이를 간과할 경우 결과가 달라지게 되니 유의하자. 

 

또한, DFS 결과값을 출력하고 BFS도 출력해야 하므로, 사용한 함수는 꼭 초기화시켜주도록 하자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool visited[1001]; //방문 여부 체크
vector <int> adj[1001]; //인접한 노드 저장
queue <int> q;
int node, line, s;

void dfs(int now) {
    visited[now] = 1;
    printf("%d ", now);
    for (int i = 0; i < adj[now].size(); i++) { //인접한 노드의 갯수만큼 반복
        int next = adj[now][i];
        if (!visited[next]) { //인접 노드가 한 번도 방문하지 않은 노드일 경우,
            dfs(next); //해당 인접 노드와 또 인접하는 노드를 찾는 것이 DFS. 그러한 이유로 재귀 사용
        }
    }
}
void bfs(int now) {
    visited[now] = 1;
    q.push(now); //큐를 만들어 현재 노드에서 인접하는 노드를 모두 저장할 수 있도록 함
    while (!q.empty()) { //큐가 비었다는 것은 전부 탐색했다는 의미
        int st = q.front(); 
        printf("%d ", st);
        q.pop(); //탐색이 끝난 노드는 pop으로 제거
        for (int i = 0; i < adj[st].size(); i++) { //인접한 노드의 갯수만큼 반복
            int next = adj[st][i];
            if (!visited[next]) { //인접 노드가 한 번도 방문하지 않은 노드일 경우,        
                visited[next] = 1; //해당 인접 노드를 큐에 넣음 = 방문했다는 의미 
                q.push(next);
            }
        }
    }
}

int main() {
    int a, b;  
    scanf("%d %d %d", &node, &line, &s);
    for (int i = 0; i < line; i++) {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i <= node; i++) {
        sort(adj[i].begin(), adj[i].end()); //오름차순 정렬
    }
    
    dfs(s);
    printf("\n");
    memset(visited, 0, sizeof(visited)); //함수 초기화
    bfs(s);

    return 0;
}

adj[i][k]에서 i는 현재 노드의 숫자 자체를, k는 인덱스를 의미한다. 만약 i가 1이라면,

 k 자리의 0번방에는 2가, 1번방에는 3이, 2번방에는 4가 들어간다. 즉 k 자리에는 인접한 노드가 0번 인덱스부터 들어있다.

 

이슈(OutOfBounds 런타임 에러) : for 반복문 종료 조건 설정

 위의 코드 중 "오름차순 정렬"이라는 주석 부분을 주목하자. adj라는 벡터는 인접한 노드의 값들을 저장한다. 그 저장한 값들을 오름차순으로 정렬해주고자 for 반복문을 사용하고 있다. 초반에는 이 반복문의 종료 조건을 "간선의 개수"만큼으로 설정했었다. 그렇게 설정하면, 노드보다 간선의 개수가 많을 때 오류를 일으킨다. 꼭 노드의 개수만큼 반복할 수 있게 코드를 작성하자.

 

 이러한 이유가 아니라면, 다른 코드에서 for 반복문 종료조건을 잘못 설정한 것은 아닌지, 벡터나 배열의 크기를 알맞게 설정했는지도 확인해보자.