[BaekJoon] 16906번 - 욱제어 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 단어들로 욱제어 단어를 모두 만들 수 있으면 욱제어 단어를 순서대로 출력하는 문제로 욱제어는 서로 접두어가 되는 관계가 없는 단어들이어야 한다. 트라이 자료구조를 활용하면 해결할 수 있는데 트라이에 해당 DFS로 해당 길이의 단어가 들어갈 수 있는 곳을 탐색하면 되며 한번이라도 새로운 노드를 만들었으면 접두어 관계에 놓이지 않게 된다. 최대한 0을 우선으로 구성해보고 안되면 이후 1을 채우는 방식으로 단어들을 채우는 그리디한 배치로 욱제어를 만들어보며 가능한지 판단할 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MX = 1 + 1000;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static int[][] nxt = new int[MX][2];
    static boolean[] chk = new boolean[MX];

    static void insert(int cur, int l, StringBuilder word) {
        if (chk[cur]) return;

        if (word.length() == l) {
            if (cur != unused - 1) return;

            chk[cur] = true;
            list.add(word.toString());
            success = true;
            return;
        }

        for (int i = 0; i < 2; i++) {
            if (nxt[cur][i] == 0) nxt[cur][i] = unused++;
            word.append((char) ('0' + i));
            insert(nxt[cur][i], l, word);
            word.deleteCharAt(word.length() - 1);

            if (success) return;  // 0으로 끝나는 욱제어 삽입 성공시 1로 끝나는 노드 삽입 방지
        }
    }

    static boolean success;  // 욱제어 삽입 성공 여부
    static List<String> list = new ArrayList<>();  // 욱제어를 저장한 리스트

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            StringBuilder word = new StringBuilder();
            success = false;

            insert(ROOT, x, word);
            if (success) continue;

            System.out.println(-1);
            return;
        }

        System.out.println(1);
        for (String word : list) {
            System.out.println(word);
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 1000;
const int ROOT = 0;
int unused = ROOT + 1;
int nxt[MX][2];
bool chk[MX];

vector<string> v;  // 욱제어를 저장한 벡터
bool success;      // 욱제어 삽입 성공 여부

void insert(int cur, int l, string& s) {
    if (chk[cur]) return;

    if (s.size() == l) {
        if (cur != unused - 1) return;

        chk[cur] = true;
        v.push_back(s);
        success = true;
        return;
    }

    for (int i = 0; i < 2; i++) {
        if (nxt[cur][i] == 0) nxt[cur][i] = unused++;
        s += '0' + i;
        insert(nxt[cur][i], l, s);
        s.pop_back();

        if (success) return;  // 0으로 끝나는 욱제어 삽입 성공시 1로 끝나는 노드 삽입 방지
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;

        string s;
        success = false;

        insert(ROOT, x, s);
        if (success) continue;

        cout << -1;
        return 0;
    }

    cout << "1\n";
    for (string& x : v) {
        cout << x << '\n';
    }
}

---