[C/C++] 화면에 출력 / BFS / 코드트리 / 실버1

코드트리 화면에 출력 문제

 

조건 : 시간제한(1초), 메모리 제한 (80MB)

 

---

 화면에 출력 풀이

1. BFS

이 문제를 풀면서 한 가지 간과한 점이 있다. 

처음 풀이를 풀 때 재귀함수로 풀이를 시작했으나, 시간초과가 뜨는 에러를 범했다. 

 

재귀함수는 DFS와 똑같이 깊이 우선 탐색이라 한 경로를 끝까지 탐색하고, 목표 상태에 도달하면  그 값을 기록한 후 다른 경로를 탐색하는 방식이기 때문에 빠르게 최적의 값을 탐색할때는 적합하지 않다.

 

따라서, BFS를 사용하면 가까운 상태부터 탐색하며, 모든 경로를 확장하는 방식인데 이 방식은 최단 경로나 최소 동작 수를 찾을 때 유리한 알고리즘이다. 목표 상태에 처음으로 도달한 순간 항상 최단 경로 또는 최소 동작 수에 해당하기 때문에 목표 상태에 도달하면 바로 종료할 수 있다. 

 

2. Tuple

이 문제에서는 조건으로 num, clip, result 값이 필요하기 때문에 tuple를 쓰는 것이 여러모로 편하다.

항상 pair만 써왔기 때문에 이 기회에 tuple을 쓰는 법 같이 같이 공부를 해봤다.

 

tuple은 특이하게 값의 인자값을 쓸 때 다르게 쓴다.

queue<tuple<int,int,int>> q;

q.push({1,2,3}); 

cout << get<0>(q.front()) << '\n'; // 1
cout << get<1>(q.front()) << '\n'; // 2
cout << get<2>(q.front()) << '\n'; // 3

 

 

3. 조건 충족 시 return

처음에 재귀를 쓰다가, BFS로 바꾸고나서 안됐던 점이 조건이 충족됐을 때 continue를 했었다는 점이다.

 

재귀는 어떤 값이 최솟값인지 모르기 때문에 계속 코드를 돌려야했는데, BFS는 그 상태에 도달하면 그 최초값이 최소이기 때문에 거기서 함수를 return 하여 종료시키면 된다. 

 

---

화면에 풀이 문제 코드

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;
int clip = 0;
int n;
int final = 0;
int minn = 10000;
queue<tuple<int,int,int>> que;
bool vis[4000][2001];
void func(int numm, int clipp, int resultt){
   

    que.push({1,0,0});
    vis[1][0] = 1;

    while(!que.empty()){
        
        
        int num = get<0>(que.front());
        int clip = get<1>(que.front());
        int result = get<2>(que.front());

        
        que.pop();
        if(num == n) {
            minn = min(minn,result);
            return;
        }
        if(!vis[num+clip][clip] && clip >0 && num+clip < 1100){
            que.push({num+clip,clip,result+1});
            vis[num+clip][clip] = 1;
        }

        if(!vis[num][num]){
            que.push({num,num,result+1});
           vis[num][num] = 1;
        }

        if(num > 1 && !vis[num-1][clip]){
            que.push({num-1,clip,result+1});
           vis[num-1][clip] = 1;
        }

        //cout << "num : " << num << " clip : " << clip << " result : " << result << '\n';
    }
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    func(1,0,0);

    cout << minn;
    return 0;
}