[백준 5014번] [BFS] 스타트링크

DFS, BFS를 처음 배운 입장에서는 좀 까다로운 문제였다.

 

이 문제를 보고 처음 접근한 방식은, DFS이다.

실제로 구현 방법이 아직까지는 DFS가 재귀로 짜기 쉽기도하고, 두 가지 방법의 근본적인 차이에 대해서 잘 이해하지 못했기 때문이다.

 

일단, 이 문제를 DFS로 바라보면 안되는 이유에 대해서 정리하자면,

 

1. 너무 불필요하게 하나의 케이스를 기준으로 건물 양 끝을 오가게 된다.

정확하게 이 문제를 이해해보면, 올라가는 케이스와 내려가는 케이스를 기준으로 해당하는 칸을 갈 수 있는지를 체크하는 것이 중요하다.

그런데, 만약에 해당하는 칸을 가면 참 좋겠지만 가지 못한다면 잘못하면 무한루프에 빠질 가능성이 존재한다.

위 문제에서 최저값이 1층 최고값이 입력에서 제한되어 있는 상황이므로 계속해서 계속해서 증가하거나 감소하는 케이스의 경우에는 결과적으로 횟수를 반복함에 따라 이 제한선에 걸리는 것을 통해 무한 루프에 빠져나갈 수 있다. 즉, 가장 먼저 확인해보아야 할 부분은 증가와 감소가 동시에 할 수 있는 상황이므로 단순히 증가, 감소하는 상황이 아니라 진동하는 상황이 존재하는지를 먼저 판단해야 한다.

 

Case1 : 올라가는 칸이 내려가는 칸보다 더 큰 경우
올라가는 칸이 내려가는 칸보다 더 큰 경우에는 결과적으로 계속해서 올라가고 내려가는 행위를 반복함에 따라서 증가하게 된다. 즉, 국소적으로 보면 진동하는 것으로 볼 수 있으나 결과적으로는 증가하므로 최고층 제한에 걸리게 된다.

Case2 : 내려가는 칸이 올라가는 칸보다 더 큰 경우
내려가는 칸이 올라가는 칸보다 더 큰 경우에는 결과적으로 계속해서 올라가고 내려가는 행위를 반복함에 따라서 감소하게 된다. 즉, 국소적으로 보면 진동하는 것으로 볼 수 있으나 결과적으로는 감소하므로 최저층 제한에 걸리게 된다.

Case3 : 올라가는 칸과 내려가는 칸이 같은 경우
이 경우에는 진짜로 진동하는 케이스가 발생하지만 visited를 활용해서 방문한 것을 지워주면 쉽게 해결할 수 있다.

즉, 결과적으로 어떠한 케이스가 주어져도 무한루프 케이스를 탈출할 수 있음을 일단은 확인할 수 있다.

그러면, 최종적으로 dfs 케이스에 대해서 검토해보면 각 케이스에 대해서 존재하는지 아닌지를 판단하기 위해서는 양 끝 값으로 이동해야하는 작업을 반드시 거쳐야 한다.

그러면 불필요하게 모든 케이스에 대해서 양 끝을 오가게 되어서 불필요한 계산이 발생하게 된다.

 

2. 결과적으로 모든 케이스를 검토해야 한다.

이 문제에서 요구하는 조건을 잘 살펴보면, "적어도 몇 번 눌러야 하는지"를 구하라고 한다.

즉, 만족하는 케이스 중 누르는 횟수의 최솟값을 출력하라는 의미이다.

그런데, DFS의 경우에는 각 node에서 해당하는 케이스가 나오더라도 나머지 node에서 더 작은 값이 존재한다는 것을 보장해주지 못한다.

즉, 이러한 측면에서 결과적으로 모든 노드들에 대해서 조사해야 한다.(적어도 같은 깊이까지는 조사해야 한다.)

 

이러한 측면에서 DFS를 이 문제에서 이용하기 힘들다.

 

반면, BFS를 이용하게 되면 이러한 모든 단점을 해결할 수 있는데, 각 node에 대해서 올라가고 내려가는 케이스를 고려하고 만약에 만족하는 케이스가 존재하면 바로 break를 밟고 해당하는 값을 출력하면 된다. 왜냐하면 BFS의 경우는 기준점을 기준으로 같은 깊이에 해당하는 모든 node들에 대한 연산을 끝내고 다음 깊이로 이동하므로 다음에 등장하는 것들은 무조건 그것보다 더 깊이가 더 크다(누른 횟수가 더 많다.) 이러한 측면에서 이 문제는 DFS보다 BFS가 유용하다.

 

단, 위에서 언급한 것처럼 BFS또한 최종적으로 만족하지 않는 케이스를 따로 처리해주기 위해서는 동일한 원리를 적용하여 최저층과 최고층 제한을 계속해서 체크만 해주면 된다.

 

위의 내용을 바탕으로 코드로 구현한 결과는 다음과 같다.

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

using namespace std;

int up, down, total;
int check_num = 2147483647;
bool visited[1000001] = {false};

int main(void){
    int current, purpose;
    cin >> total >> current >> purpose >> up >> down; // 문제에서 입력하는 값
    queue <pair<int,int> > bfs;

    pair<int,int> first_element; // 층을 first element, 이동횟수를 second element
    first_element.first = current;
    first_element.second = 0;
    bfs.push(first_element);
    visited[current] = 1;

    while(bfs.size() != 0){
        if(bfs.front().first == purpose){
            check_num = bfs.front().second;
            break; // 만약 가장 앞에 있는 것이 목적하는 것이라면, 이동횟수 저장
        }
        else{
            int temp = bfs.front().first;
            int depth_temp = bfs.front().second;
            bfs.pop();
            pair<int,int> up_case;
            pair<int,int> down_case; // up_case와 down_case를 각각 판단
            up_case.first = temp + up;
            up_case.second = depth_temp + 1;
            down_case.first = temp - down;
            down_case.second = depth_temp + 1;

            if(temp + up > total && temp - down <= 0){ // 범위 초과 check
                break;
            }
            else if(temp + up > total){
                if(visited[down_case.first] == false){
                    bfs.push(down_case);
                    visited[down_case.first] = true;
                }
                
            }
            else if(temp - down <= 0){
                if(visited[up_case.first] == false){
                    bfs.push(up_case);
                    visited[up_case.first] = true;
                }
            }
            else{
                if(visited[down_case.first] == false){
                    bfs.push(down_case);
                    visited[down_case.first] = true;
                }
                if(visited[up_case.first] == false){
                    bfs.push(up_case);
                    visited[up_case.first] = true;
                }
            }
        }
    }

    if(check_num != 2147483647){
        cout << check_num << "\n";
    }
    else{
        cout << "use the stairs\n";
    }

}

이 문제를 통하여, BFS와 DFS의 차이를 정확하게 인식하고 복습하도록 하자.