딩코딩 : Computer Science 블로그

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

트라이의 성질을 이용하여 트리구조를 구현해야한다.

이때 출력은 사전순으로 해야하기 때문에

자바로 문제를 푸는 경우엔 TreeMap을 활용하면 key값을 기준으로 알아서 정렬이 된다.

출력은 정렬된 TreeMap을 활용해 하위 노드들을 중위순회로 돌면 된다.

//package org.example;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    class Trie {
        TreeMap<String, Trie> child = new TreeMap<>();
    }
    //출력용
    private StringBuilder sb = new StringBuilder();
    public void print(Trie root, int depth) {
        Set keys = root.child.keySet();

        for (Object key : keys) {
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            sb.append(key).append("\n");
            print(root.child.get(key), depth + 1);
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Trie root = new Trie();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int K = Integer.parseInt(st.nextToken());

            Trie cur = root;
            //Trie 생성
            for (int j = 0; j < K; j++) {
                String str = st.nextToken();
                if (!cur.child.containsKey(str)) {
                    cur.child.put(str, new Trie());
                }
                cur = cur.child.get(str);
            }
        }
        print(root, 0);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    final int GO_MX = 10;

    class Trie {
        Trie[] go;
        boolean output;
        boolean hasChild;

        public Trie() {
            go = new Trie[GO_MX];
            Arrays.fill(go, null);
            output = hasChild = false;
        }

        public void insert(String str, int level) {
            if (level == str.length()) {
                output = true;
                return;
            }
            int next = str.charAt(level) - '0';

            if (go[next] == null) go[next] = new Trie();
            hasChild = true;

            go[next].insert(str, level + 1);
        }

        public boolean consistent() {
            if (this.hasChild && this.output) return false;

            for (int i = 0; i < GO_MX; i++) {
                if (go[i] != null && !go[i].consistent()) return false;
            }

            return true;
        }
    }


    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            Trie trie = new Trie();
            for (int j = 0; j < n; j++) {
                String str = br.readLine();
                trie.insert(str, 0);
            }


            if (trie.consistent()) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

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

#include <iostream>
#include <algorithm>

#define MX 100003

typedef long long ll;
using namespace std;

const int mod = 1e9;
ll N, M, unf[MX];
ll sum = 0, ans = 0;

struct Edge {
    int x, y, w;

    bool operator<(const Edge &b) const {
        return w > b.w;
    }
};

Edge edges[MX];


int Find(int x) {
    if (unf[x] < 0) return x;
    return unf[x] = Find(unf[x]);
}

ll Union(int a, int b) {
    ll ret = unf[a] * unf[b];
    if (unf[a] < unf[b]) {
        unf[a] += unf[b];
        unf[b] = a;
    } else {
        unf[b] += unf[a];
        unf[a] = b;
    }
    return ret;
}

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

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        unf[i] = -1;
    }

    for (int i = 0; i < M; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        edges[i] = {x, y, w};
        sum += w;
    }

    sort(edges, edges + M);

    for (int i = 0; i < M; i++) {
        auto [x, y, w] = edges[i];
        x = Find(x);
        y = Find(y);

        if (x != y) {
            ans += sum * Union(x, y);
        }
        ans %= mod;
        sum -= w;
    }
    cout << ans << '\n';
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int N;
//i+j, i-j
bool arr[16], diagonal1[32], diagonal2[55];
int ans = 0;

void backTrack(int L) {
    if (L == N) {
        ans++;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!arr[i] && !diagonal1[L + i] && !diagonal2[L - i + N]) {
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 1;
            backTrack(L + 1);
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 0;
        }
    }
}


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

    cin >> N;
    backTrack(0);
    cout << ans << '\n';

}

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

1. 문제설명

BFS를 돌면서 모든 노드간 간선의 가중치를 구하고,

크루스칼을 시행하면된다.

이렇게 풀 수 있는 이유는 복제 로봇이 시작점, 키가 있는 곳에서 무한으로 복제가 가능하기 때문에

모든 노드를 이어놓고 최소스패닝트리를 구하면 답이 되기 때문이다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M;
string arr[51];
int maze[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

struct Edge {
    int from, to, weight;
    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }

};


vector<pair<int, int> > vertex;
vector<Edge> edge;

bool BFS(int num) {
    int x = vertex[num].first;
    int y = vertex[num].second;

    int check[51][51];
    memset(check, 0, sizeof(check));

    check[x][y] = 1;
    queue<pair<int, int> > Q;
    Q.push({x, y});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (check[nx][ny] || maze[nx][ny] == -1) continue;
            check[nx][ny] = check[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }

    for (int i = num + 1; i < vertex.size(); i++) {
        int nx = vertex[i].first;
        int ny = vertex[i].second;

        if (check[nx][ny] == 0) {
            return false;
        }
        edge.push_back({num, i, check[nx][ny] - 1});
    }


    return true;
}


//kruskal
int unf[3000];

int Find(int a) {
    if (unf[a] < 0) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


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

    cin >> N >> M;

    int kidx = 2;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == '1') {
                maze[i][j] = -1;
            } else if (arr[i][j] == 'S') {
                maze[i][j] = 1;
                vertex.push_back({i, j});
            } else if (arr[i][j] == 'K') {
                maze[i][j] = kidx++;
                vertex.push_back({i, j});
            }
        }
    }


    //각 노드간 edge 생성
    for (int i = 0; i < vertex.size() - 1; i++) {
        if (!BFS(i)) {
            //연결되지 않은 vertex 존재할 경우
            cout << -1 << '\n';
            return 0;
        }
    }


    //크루스칼
    int ans = 0;
    memset(unf, -1, sizeof(unf));
    sort(edge.begin(), edge.end());

    for (auto e: edge) {
        auto [a, b, c] = e;
        a = Find(a);
        b = Find(b);

        if (a != b) {
            Union(a, b);
            ans += c;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

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

#include <bits/stdc++.h>

#define MX 10001
using namespace std;

int N, P;

struct Edge {
    int from, to, weight;

    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }
};

int countryCost[MX], unf[MX];
vector<Edge> realEdges;

int Find(int a) {
    if (unf[a] < 0) {
        return a;
    }
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


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

    cin >> N >> P;

    memset(unf, -1, sizeof(unf));

    int minCountry = 1e9;
    for (int i = 1; i <= N; i++) {
        cin >> countryCost[i];
        minCountry = min(minCountry, countryCost[i]);
    }

    for (int i = 1; i <= P; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        realEdges.push_back({a, b, 2 * c + countryCost[a] + countryCost[b]});
    }

    sort(realEdges.begin(), realEdges.end());

    int ans = 0;

    for (auto edge: realEdges) {
        auto [a, b, c] = edge;
        int aa = Find(a);
        int bb = Find(b);

        if (aa != bb) {
            Union(aa, bb);
            ans += c;
        }
    }


    cout << ans + minCountry << '\n';

    return 0;
}

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

#include <bits/stdc++.h>

#define MX 101
using namespace std;


int N, K, ans, seq[22];
bool chk[22];
string arr[22];
char resArr[400];

int fail[200];

void getFail() {
    memset(fail, 0, sizeof(fail));
    int len = strlen(resArr);
    for (int j = 0, i = 1; i < len; i++) {
        while (j > 0 && resArr[i] != resArr[j]) {
            j = fail[j - 1];
        }
        if (resArr[i] == resArr[j]) {
            fail[i] = ++j;
        }
    }
}

int KMP() {
    int ans = 0;
    int len = strlen(resArr);
    for (int i = 0; i < len; i++) {
        resArr[i + len] = resArr[i];
    }

    int patternLen = len;
    len = strlen(resArr);
    for (int j = 0, i = 0; i < len - 1; i++) {
        while (j > 0 && resArr[j] != resArr[i]) {
            j = fail[j - 1];
        }
        if (resArr[i] == resArr[j]) {
            if (j == patternLen - 1) {
                ans++;
                j = fail[j];
            } else {
                j++;
            }

        }
    }


    return ans;
}


void makeSequence(int L) {
    if (L == N) {
        int idx = 0;
        memset(resArr, 0, sizeof(resArr));
        for (int i = 0; i < N; i++) {
            string curStr = arr[seq[i] - 1];
            int strLen = curStr.length();
            for (int j = 0; j < strLen; j++) {
                resArr[idx++] = curStr[j];
            }
        }
        getFail();
        if (KMP() == K) {
            ans++;
        }
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            chk[i] = 1;
            seq[L] = i;
            makeSequence(L + 1);
            chk[i] = 0;
        }
    }

}


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

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    cin >> K;

    makeSequence(0);

    cout << ans << '\n';


    return 0;
}

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

#include <bits/stdc++.h>

#define MX 101
using namespace std;

int N, dp[MX][11][11][11];
char AC[MX], BC[MX];
int A[MX], B[MX];


int dpf(int now, int x, int y, int z) {
    if (now == N) return 0;
    int &ret = dp[now][x][y][z];
    if (ret != -1) return ret;

    ret = 1e9;

    //현재 다른 칸 수
    int df = (B[now] - x + 10) % 10;
    //돌려야 할 칸 수 왼쪽, 오른쪽
    int d[2] = {df, 10 - df};

    // x는 d[0] 이나 d[1]만큼 돌리고, y는 0~d[0] 0~d[1] 만큼 돌릴 수 있고, z는 0~j만큼 돌릴 수 있다.
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= d[i]; j++) {
            for (int k = 0; k <= j; k++) {
                //x를 왼쪽으로 돌리는 경우와 오른쪽으로 돌리는 경우를 구분
                int yy = (y + (i ? -j : j) + 10) % 10;
                int zz = (z + (i ? -k : k) + 10) % 10;

                //전체 돌리는 횟수 계산
                int val = dpf(now + 1, yy, zz, A[now + 3]);
                val += ((d[i] - j + 2) / 3 + (j - k + 2) / 3 + (k + 2) / 3);
                ret = min(ret, val);
            }
        }
    }
    return ret;
}


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

    cin >> N >> AC >> BC;
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < N; i++) {
        A[i] = AC[i] - '0';
        B[i] = BC[i] - '0';
    }

    cout << dpf(0, A[0], A[1], A[2]) << '\n';
    return 0;
}