📙[Algo] 24.08.15 ~ 24.08.17 알고리즘

알고리즘 문제) BOJ 14725. 개미굴

• 링크 : https://www.acmicpc.net/problem/14725

문제 요약

• 로봇 개미로부터 얻은 개미굴 저장소를 바탕으로, 개미굴 구조를 출력해라
• 예를들어, 아래와 같은 정보를 받았다면
  • KIWI BANANA
  • KIWI APPLE
  • APPLE APPLE
  • APPLE BANANA KIWI
• 아래처럼 출력해라 APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA
• 개미굴의 각 층은 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다

시간 제한

• 1초

입력

• 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개
• 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K (1 ≤ K ≤ 15)가 주어지며,
  • 다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 1 ≤ t ≤ 15를 만족한다

출력

• 개미굴의 시각화된 구조를 출력
  • 개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다

접근법

• 트라이 자료구조를 활용해서 각 노드마다 자식 노드의 먹이를 Key값으로 갖고, 자식노드객체를 Value값으로 갖는 map과 현재 먹이가 존재하는 층을 저장했다
• 이후 로봇개미로부터 받은 먹이정보를 리스트에 담아서, 트라이 자료구조에 삽입했다.
  • 이때, 정보는 위층부터 아래층 순서대로 입력받게 되므로, 리스트에도 위층부터 순서대로 저장된다.
  • 따라서, 저장할떄, 각 노드의 floor(층)값은 곧 인덱스 값이 되도록 했다
• 이후, 개미굴 구조는 search함수를 통해 출력했다
  • 매개변수로 현재 가리키는 노드를 넘겨주며, 처음에는 루트노드부터 시작했다.
  • entrySet함수를 사용해 현재 정점의 자식노드의 key값(먹이단어)를 순회
    • 이떄, 층의 개수만큼 “—”를 단어 앞에 추가해야하므로, 제일 먼저 StringBuilder메소드에 floor만큼 “—”문자열을 추가했다.
    • StringBuilder메소드에 해당 단어를 담아주었고, 그다음 자식노드를 다시 매개변수로 넘겨 재귀호출했다.

코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static class Node {
        Map<String, Node> child = new TreeMap<>();
        int floor = 0;
    }

    static class Trie {
        Node root;

        Trie() {
            this.root = new Node();
        }

        public void insert(ArrayList<String> lst) {
            Node cur = this.root;

            String str;
            for (int i = 0, len = lst.size(); i < len; i++) {
                str = lst.get(i);
                cur.child.putIfAbsent(str, new Node());
                cur = cur.child.get(str);
                cur.floor = i;
            }
        }

        public void search(Node cur) {
            String key;
            for (Map.Entry<String, Node> entry : cur.child.entrySet()) {
                key = entry.getKey();
                for (int i = 0; i < cur.child.get(key).floor; i++) {
                    sb.append("--");
                }
                sb.append(key).append("\\n");
                search(cur.child.get(key));
            }
        }
    }

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

        Trie trie = new Trie();

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

        int K;
        ArrayList<String>[] lst = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            lst[i] = new ArrayList<>();
            for (int j = 0; j < K; j++) {
                lst[i].add(st.nextToken());
            }
            trie.insert(lst[i]);
        }

        trie.search(trie.root);

        System.out.println(sb);

    }
}

 

알고리즘 문제) BOJ 22856. 트리 순회

• 링크 : https://www.acmicpc.net/problem/22856

문제 요약

• 노드 N개인 이진트리
• 이때, 유사 중위 순회를 진행할 때, 이동한 횟수를 구해라
  • 현재 위치한 노드의 왼쪽 자식 노드가 존재하고, 아직 방문하지 않았다면 해당 노드로 이동
  • 그렇지 않고, 현재 위치한 노드의 오른쪽 자식 노드가 존재하고, 아직 방문하지 않았다면, 해당 노드로 이동
  • 그렇지 않고, 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회 종료
  • 그렇지 않고, 부모 노드가 존재한다면, 부모 노드로 이동
  • 유사 중위 순회를 종료할 때까지 위 과정 반복

시간 제한

• 1초

입력

• 트리를 구성하는 노드의 개수 N
• N+1 번째 줄까지 현재 노드 a, 현재 노드의 왼쪽 자식 노드 b, 현재 노드의 오른쪽 자식 노드 c가 공백으로 구분되어 주어진다.
  • 만약 자식 노드의 번호가 -1인 경우 자식 노드가 없다는 것을 의미

출력

• 유사 중위 순회를 하면서 이동한 총 횟수를 출력

접근법

• 우선 중위순회의 마지막노드에 방문하게 되면 더이상 유사중위순회를 진행하지 않으므로, 중위순회할 때 마지막 노드를 미리 last 변수에 저장한다
• 이후, 루트노드1부터 유사중위순회를 진행하면서
  • 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 방문하지 않았다면, 방문하여 재귀호출하여 해당 자식노드로 이동한다
  • 만약 더 이상 방문할 자식 노드가 없다면 현재 노드 방문체크 true하고, 해당 노드의 부모노드로 이동한다
  • 이렇게 순회하다보면, last 노드를 방문하는 순간이 오는데, 이때, last노드를 이미 방문한 경우에는 더 이상 부모 노드로 이동하지 않도록 조건을 걸어둔다.
    • 즉, 이미 last노드의 자식노드까지 탐방을 마친 경우, last노드부터 더 이상 부모노드로의 이동을 막는 것이다.

코드

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

public class Main {
    static int N;
    static Node[] tree;
    static int[] parent;
    static boolean[] visited;
    static int last;

    static class Node {
        int leftNode;
        int rightNode;

        Node(int leftNode, int rightNode) {
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
    }

    static public int search(int cur) {

        int ret = 0;

        if (tree[cur].leftNode != -1 && !visited[tree[cur].leftNode]) {
            // 왼쪽 자식 노드가 존재하고, 방문하지 않았다면 해당 노드로 이동
            ret += search(tree[cur].leftNode) + 1;
        }

        if (tree[cur].rightNode != -1 && !visited[tree[cur].rightNode]) {
            // 오른쪽 자식 노드가 존재하고, 방문하지 않았다면 해당 노드로 이동
            ret += search(tree[cur].rightNode) + 1;
        }

        // 부모 노드로 이동
        visited[cur] = true;
        // 이미 중위순회에 마지막 노드까지 방문했다면 더이상 부모로 이동 X
        if (!visited[last]) ret += search(parent[cur]) + 1;

        return ret;
    }

    static void inorder(int v) {
        if (v == -1) return;

        inorder(tree[v].leftNode);
        last = v;
        inorder(tree[v].rightNode);
    }

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

        N = Integer.parseInt(br.readLine());

        tree = new Node[N + 1];
        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }
        visited = new boolean[N + 1];

        int a, b, c;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            tree[a] = new Node(b, c);
            if (b != -1) parent[b] = a;
            if (c != -1) parent[c] = a;
        }

        // 중위순회의 마지막 노드 찾기
        inorder(1);

        // 루트 노드는 항상 1번
        System.out.println(search(1));
    }
}

 

알고리즘 문제) BOJ 13244. 트리

• 링크 : https://www.acmicpc.net/problem/13244

문제 요약

• 주어진 그래프가 트리인지 파악하라
• 트리 조건
  • 모든 노드는 다른 노드에 도달 가능
  • 간선을 제거하면, 일부 노드에 도달할 수 없게 됨
  • 만약 기존 두 노드 사이에 간선

시간 제한

• 2초

입력

• 그래프 수 T
• 각 테케별로
  • 그래프 노드 수 N
    • 1 ≤ N ≤ 1000
  • 간선 수 M
    • 1 ≤ M ≤ 100만
  • M개의 줄에 연결된 두 노드 a, b가 주어짐
  • 모든 테케의 M의 합은 최대 100

출력

• 각 그래프에 대해, 그 그래프가 트리인 경우 "tree"를, 그렇지 않은 경우 "graph"를 한 줄로 출력

접근법

• 하나의 연결 요소일 것
  • Union & Find를 사용하여 연결된 노드들로 하나의 연결요소로 묶어준 후, 각 노드가 속해있는 연결요소의 parent노드가 모두 일치하지 않은경우는 graph로 판단
• 간선 개수 = 노드 개수 - 1 일 것
• 위 2조건을 만족하는 경우에만 tree

코드

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

public class Main {
    static int N, M;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    static boolean isTree() {
        boolean ret = true;

        int p = find(1);
        for (int i = 2; i <= N; i++) {
            if (p != find(i)) {
                ret = false;
                break;
            }
        }

        return ret && (M == N - 1);
    }

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

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

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            M = Integer.parseInt(br.readLine());

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

            int a, b;
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());

                union(a, b);
            }

            if (isTree()) sb.append("tree\\n");
            else sb.append("graph\\n");
        }

        System.out.println(sb);
    }
}

 

알고리즘 문제) BOJ 12919. A와 B 2

• 링크 : https://www.acmicpc.net/problem/12919

문제 요약

• 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임
• 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능
  • 문자열의 뒤에 A를 추가
  • 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다

시간 제한

• 2초

입력

• 첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

• S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

접근법

• 그냥 S부터 탐색을 시작해서 T가 될 수 있는 모든 경우의 수를 살펴 보게되면 시간초과가 뜬다. ⇒ 2의 N승만큼 탐색
• 따라서 역으로 T에서 S로 가는 방향으로 생각해서 풀었다
  • 즉, 역으로 생각할 때는
    • 현재 문자열의 맨 뒤에 A가 있는 경우에 1번 연산을 역으로 계산
    • 현재 문자열의 맨 앞에 B가 있는 경우에 2번 연산을 역으로 계산
  • 하기 때문에 불필요한 케이스는 필터링하면서 탐색이 가능해진다.

코드

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

public class Main {
    static String S, T;

    static int makeStr(StringBuilder sb) {
        if (String.valueOf(sb).equals(S)) return 1;
        if (sb.length() <= 0) return 0;

        int ret = 0;

        String org = String.valueOf(sb);

        // 1번 연산 -> 만약 문자열 맨 뒤에 A가 있다면, 해당 글자 제거하기
        if (sb.charAt(sb.length() - 1) == 'A') ret += makeStr(sb.deleteCharAt(sb.length() - 1));

        // 2번 연산 -> 만약 문자열 맨 앞에 B가 있다면, 해당 글자 제거 후 뒤집기
        sb = new StringBuilder(org);
        if (sb.charAt(0) == 'B') ret += makeStr(sb.deleteCharAt(0).reverse());

        return ret;
    }

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

        S = br.readLine();
        T = br.readLine();

        int ret = makeStr(new StringBuilder(T));

        if (ret > 0) System.out.println(1);
        else System.out.println(0);
    }
}

 

알고리즘 문제) BOJ 13164. 행복 유치원

• 링크 : https://www.acmicpc.net/problem/13164

문제 요약

• 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다
• 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다
• 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다
• 최소의 비용을 구하자

시간 제한

• 1초

입력

• 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다
• 음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다
  • 원생의 키는 10^9를 넘지 않는 자연수

출력

• 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력

접근법

• 인접해있는 원생간 키 차이를 담은 dist배열 생성
  • 그러면 dist배열 크기는 N-1이 된다.
• 이때, K그룹으로 나누기 위해서는 차이값 개수 N-1 중 k-1개를 제외하고 선택해야한다.
• 따라서, dist배열에서 가장 큰 차이값 K-1개를 제외한 나머지 차이값들의 합이 정답이 된다.

코드

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dist = new int[N - 1];
        int sum = 0;
        for (int i = 0; i < N - 1; i++) {
            dist[i] = arr[i + 1] - arr[i];
            sum += dist[i];
        }

        Arrays.sort(dist);

        int idx = N - 2, minusSum = 0;
        while (idx >= N - K) {
            minusSum += dist[idx];
            idx--;
        }

        System.out.println(sum - minusSum);
    }
}

 

알고리즘 문제) BOJ 17352. 여러분의 다리가 되어 드리겠습니다!

• 링크 : https://www.acmicpc.net/problem/17352

문제 요약

• 선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다.
• 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.
• 이때, 다리 하나가 부러졌다!!!
• 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라

시간 제한

• 1초

입력

• 첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)
• 그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

출력

• 다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

접근법

• 2개의 연결요소를 하나로 합쳐야 하기 때문에, union & find를 통해 같은 연결요소로 묶은 뒤, find함수로 서로 다른 연결요소인 경우를 찾아, 각 연결요소의 아무 노드 하나씩 출력했다.

코드

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

public class Main {
    static int N;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if (a == b) return;

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

        N = Integer.parseInt(br.readLine());

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

        int a, b;
        for (int i = 0; i < N - 2; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        int v1 = find(1), v2 = 0;
        for (int i = 2; i <= N; i++) {
            if (v1 != find(i)) {
                v2 = i;
                break;
            }
        }

        System.out.println(v1 + " " + v2);
    }
}

 

알고리즘 문제) BOJ 14945. 불장난

• 링크 : https://www.acmicpc.net/problem/14945

문제 요약

• 랩실의 바닥은 길이가 1인 정사각형 모양의 타일들로 이루어져 있고, 랩실은 아래 그림과 같은 직각삼각형 모양이다
• 랩실 구석 타일 위에 붙은 불은 매 초마다 가로, 세로 그리고 대각선 방향으로 한 타일씩 번진다.
• 기웅이와 민수는 불이 타오르기 딱 1초 전에 불이 붙은 타일에서 도망가기 시작했다.
• 기웅이와 민수는 1초에 아래 방향, 또는 오른쪽 아래 대각선으로만 한 칸을 움직일 수 있다.
• 처음 불장난을 하던 타일을 제외하고 두 사람이 같은 타일 위에 선다면 두 사람은 부딪혀서 넘어지게 된다.
• 두 사람이 모두 안전하게 방을 탈출하는 경우의 수를 구해보자
• 아래는 N이 5인 경우 랩실 구조
  

  

시간 제한

• 1초

입력

• 방의 한 모서리의 길이 n이 나온다. (1 < n ≤ 100)

출력

• 두 사람이 안전하게 방을 빠져나오는 경우의 수를 10,007로 나눈 나머지를 출력한다.

접근법

• 현재 두 사람의 행 위치 r과 각각 열 위치 c1, c2를 매개변수로 넘기면서, 아래 혹은 대각선아래로 이동하며 r이 N이 될때까지 탐색한다
  • 두 사람 각각 아래, 아래 대각선을 이동하므로, 4의 n승 가지가 나온다.
• 이때, 둘이 같은 위치에 있는 경우 c1 == c2 는 0을 리턴하여, 가지치기했다
• 최종적으로 r이 N에 도달했을 때 탈출에 성공한 것으로 판단해서 1을 리턴했다
• 4의n승을 최적화하기 위해 이미 탐색한 경우의 수는 dp배열에 저장해두었다
  • 즉 dp[r][c1][c2]는 r행에 두사람이 c1, c2에 위치한 경우의 경우의 수 값을 저장한다.

코드

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

public class Main {
    static int N;
    static final int MOD = 10_007;
    static int[][][] dp;

    static int recur(int r, int c1, int c2) {

        if (r != 1 && c1 == c2) return 0;

        if (r == N) return 1;

        if (dp[r][c1][c2] != -1) return dp[r][c1][c2];

        int ret = 0;

        ret = (ret + recur(r + 1, c1,  c2 + 1) % MOD) % MOD;
        ret = (ret + recur(r + 1, c1, c2) % MOD) % MOD;
        ret = (ret + recur(r + 1, c1 + 1, c2) % MOD) % MOD;
        ret = (ret + recur(r + 1, c1 + 1, c2 + 1) % MOD) % MOD;

        dp[r][c1][c2] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        dp = new int[110][110][110];
        for (int[][] d1 : dp) {
            for (int[] d2 : d1) {
                 Arrays.fill(d2, -1);
            }
        }

        int ret = recur(1, 1, 1);
        System.out.println(ret);
    }
}

 

알고리즘 문제) BOJ 7432. 디스크 트리

• 링크 : https://www.acmicpc.net/problem/7432

문제 요약

• 상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)
• 다음 N개 줄에는 디렉토리 경로가 주어진다
  • 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다
  • 경로는 80글자를 넘지 않으며, 디렉토리는 역슬래시(\)로 구분된다

출력

• 디렉토리 구조를 보기 좋게 출력
  • 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미
  • 각 서브 디렉토리는 사전순으로 출력

접근법

• 개미굴 문제와 동일하게 접근

코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static class Node {
        Map<String, Node> child = new TreeMap<>();
        int line = 0;
    }

    static class Trie {
        Node root;

        Trie() {
            this.root = new Node();
        }

        public void insert(String[] name) {
            Node cur = this.root;

            String str;
            for (int i = 0, len = name.length; i < len; i++) {
                str = name[i];
                cur.child.putIfAbsent(str, new Node());
                cur = cur.child.get(str);
                cur.line = i + 1;
            }
        }

        public void search(Node cur) {
            for (String key : cur.child.keySet()) {
                for (int i = 0; i < cur.line; i++) sb.append(" ");
                sb.append(key);
                sb.append("\\n");
                search(cur.child.get(key));
            }
        }

    }

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

        Trie trie = new Trie();

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

        String[] str;
        for (int i = 0; i < N; i++) {
            // \\ 기준으로 구붙하기
            str = br.readLine().split("\\\\\\\\");
            trie.insert(str);
        }

        trie.search(trie.root);

        System.out.println(sb);
    }
}