uva 679 - Dropping Balls

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=620

 

FBT 는 배열로 쉽게 표현가능합니다.

 

현재 위치를 flag 로 표현할 때, 

좌 -> 우 로 자식노드를 확인해주면서 마지막 리프노드에 도달하는 순서를 확인하는 문제입니다.

좌 가 false 이면 방문 true 이면 우 를 확인

우 가 false 이면 방문 true 이면 둘다 false 갱신 후 좌 부터 진입

 

재귀를 이용했습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
 
int deep;
int visit[1 << 20];
 
void dfs(int node, int now_cnt, int cnt) {
    if (node >= (1 << (deep - 1)) && now_cnt == cnt) {
        cout << node << "\n";
        return;
    }
 
    if (node >= (1 << (deep - 1))) {
        visit[node] = 1;
        return;
    }
 
    visit[node] = 1;
 
    if (!visit[node * 2]) dfs(node * 2, now_cnt, cnt);
    else if (!visit[node * 2 + 1]) dfs(node * 2 + 1, now_cnt, cnt);
    else {
        visit[node * 2] = visit[node * 2 + 1] = 0;
        dfs(node * 2, now_cnt, cnt);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--) {
        int cnt;
        cin >> deep >> cnt;
 
        for (int i = 1; i <= cnt; i++)
            dfs(1, i, cnt);
 
        memset(visit, 0, sizeof(visit));
    }
    int num = -1;
    cin >> num;
 
    return 0;
}