GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리의 독립집합 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2213

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        Graph graph = new Graph(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) graph.addWeight(i, parseInt(st.nextToken()));
        
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken()));
        }

        graph.run();
    }    
}

class Graph {
    int n;
    Node[] nodes; // 노드 배열
    Queue<Node> queue = new PriorityQueue<>(Comparator.comparing((Node n) -> n.x)); // 독립 집합
    int[] dp, arr, selected; // dp, arr(집합의 가중치), 선택된 배열
    
    Graph (int n) {
        this.n = n;
        nodes = new Node[n + 1]; // 노드 배열
        dp = new int[n + 1];
        arr = new int[n + 1];
        selected = new int[n + 1];
        
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
    }
    
    class Node {
        int x; // 노드 번호
        List<Node> adjacent = new ArrayList<>(); // 인접 노드
        List<Node> tree = new ArrayList<>(); // 트리
        Node (int x) {
            this.x = x;
        }
    }
    
    void addWeight (int x, int w) {
        arr[x] = w;
    }
    
    void addEdge(int x, int y) {  // 양뱡향 연관 관계
        Node n1 = nodes[x];
        Node n2 = nodes[y];
        
        n1.adjacent.add(n2);
        n2.adjacent.add(n1);
    }
    
    void run() {
        buildTree(nodes[1], nodes[0]);

        StringBuilder sb = new StringBuilder();
        int t1 = dp(nodes[1], 0); // 루트 포함 X
        int t2 = dp(nodes[1], 1); // 루트 포함
        
        if (t1 < t2) selected[1] = 1; // 만약 포함이 더 크다면 1
        else selected[1] = 0; // 아니라면 0
        sb.append(Math.max(t1, t2)).append("\n");
        
        trace(nodes[1], selected[1]); // 1번 노드에 대한 선택 여부로 추적
        
        while(!queue.isEmpty()) {
            sb.append(queue.poll().x).append(" "); // 큐의 노드 번호를 sb에 추가
        }

        System.out.println(sb);
    }

    void buildTree(Node now, Node parent) { // 트리 만들기, 현재 노드, 부모 노드
        for (Node child : now.adjacent) { // 현재 노드의 인접 노드
            if (child != parent) { // 부모 노드라면 무한 루프이므로 제거
                now.tree.add(child); // 트리에 추가
                buildTree(child, now); // 재귀 호출
            }
        }
    }
    
    int dp(Node now, int include) {
        int ans = 0;

        if (include == 1) {
            for (Node next : now.tree) ans += dp(next, 0); // 다음 노드는 포함하지 않음
            return ans + arr[now.x];
        } else {
            for (Node next : now.tree) {
                int t1 = dp(next, 0); // 현재 포함 안한 경우 다음에도 포함 안할 수 있음
                int t2 = dp(next, 1); // 다음은 포함하도록 
                
                if (t1 < t2) selected[next.x] = 1; // 포함이 더크면 포함 처리
                else selected[next.x] = 0; // 미포함 처리
                ans += Math.max(t1, t2);
            }
            return ans;
        }
    }
    
    void trace(Node now, int include) {
        if (include == 1) { // 현재를 포함했다면
            queue.add(now); // 큐에 추가하기
            for (Node next : now.tree) trace(next, 0); // 다음은 무조건 불가
        }
        else if (include == 0) {
            for (Node next : now.tree) trace(next, selected[next.x]); // 다음은 dp의 더 큰 값에 따라 달라짐
        }
    }
}

2. 풀이 중점 사항 

독립 집합은 그래프 이론에서 어떤 두 꼭짓점도 서로 인접하지 않는 그래프에 있는 꼭짓점들의 집합을 의미합니다. 이는 곳 간선으로 직접적으로 인접해 있지 않은 노드들을 의미합니다. 트리의 독립집합을 구하는 알고리즘은 일반적인 그래프에서 NP - 하드 문제로 알려져 있습니다.

이 문제를 해결하기 위해, 트리 구조, DP, 재귀의 방식이 사용 되었습니다.

저는 한 번에 해결하지 못하여, 하단의 블로그를 참고하였습니다.

주요 소스는 다음과 같습니다.

트리 

void buildTree(Node now, Node parent) { // 트리 만들기, 현재 노드, 부모 노드
    for (Node child : now.adjacent) { // 현재 노드의 인접 노드
        if (child != parent) { // 부모 노드라면 무한 루프이므로 제거
            now.tree.add(child); // 트리에 추가
            buildTree(child, now); // 재귀 호출
        }
    }
}

인접한 노드들 간에 트리 구조를 형성하기 위해 buildTree를 토대로 현재 노드, 부모 노드를 인자로 받았습니다.

만약 현재 노드의 인접한 노드 중 부모 노드가 다시 tree로 설정된다면 무한 루프에 빠질 수 있습니다. 따라서, 부모 노드를 제외하고 트리를 추가한 후 재귀로 호출하였습니다.

dp 

int dp(Node now, int include) {
    int ans = 0;

    if (include == 1) {
        for (Node next : now.tree) ans += dp(next, 0); // 다음 노드는 포함하지 않음
        return ans + arr[now.x];
    } else {
        for (Node next : now.tree) {
            int t1 = dp(next, 0); // 현재 포함 안한 경우 다음에도 포함 안할 수 있음
            int t2 = dp(next, 1); // 다음은 포함하도록 
            
            if (t1 < t2) selected[next.x] = 1; // 포함이 더크면 포함 처리
            else selected[next.x] = 0; // 미포함 처리
            ans += Math.max(t1, t2);
        }
        return ans;
    }
}

특정 스티커를 선택해야 할 때, 인접한 스티커를 선택하지 못하는 DP 문제가 있습니다. 이 소스도 그러한 원리와 비슷하다고 볼 수 있습니다. include는 현재 선택된 노드인지를 알려주는 지표로, 만약 선택했다면 다음 노드는 선택할 수 없습니다.

반면 현재 선택되지 않았다면, 다음에도 역시 선택 안 할 수 있고 선택할 수도 있습니다.

예를 들어 [1, 100, 10, 5, 200]이 있다면, 인접하지 않게 골라야 할 때, 100을 골랐다고 해서 반드시 10을 고를 필요는 없는 것과 동일합니다. 따라서, 두 가지 경우를 파악한 후 더 큰 곳에 포함 처리하도록 하였습니다.

이상으로 백준 트리의 독립 집합 자바 풀이를 마치도록 하겠습니다.

감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리 DP 문제 트리와 쿼리 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/15681

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int r = parseInt(st.nextToken());
        int q = parseInt(st.nextToken());
        
        Graph graph = new Graph(n, r);
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken()));           
        }
        
        for (int i = 0; i < q; i++) graph.addQuery(parseInt(br.readLine()));
        
        graph.makeSubTree(r); // 서브 트리 만들며 dp 저장
        graph.getPrint(); // 결과 출력
    }
}

class Graph {
    int n; // n개의 노드
    int root; // 루트 노드
    Node[] nodes; // 노드 저장
    List<Integer> querys = new ArrayList<>(); // 출력해야하는 쿼리
    int[] dp; // 서브 트리 개수
    
    Graph (int n, int root) {
        this.n = n;
        this.root = root;
        nodes = new Node[n + 1];
        dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
    }
    
    class Node {
        int x;
        List<Node> adjacent = new ArrayList<>(); // 인접 노드
        
        Node (int x) {
            this.x = x;
        }
    }
    
    void addEdge(int x, int y) {
        Node n1 = nodes[x];
        Node n2 = nodes[y];
        
        n1.adjacent.add(n2);
        n2.adjacent.add(n1);
    }
    
    void addQuery(int x) {
        querys.add(x);
    }
    
    void makeSubTree(int root) {
        dp[root] = 1; // 서브 트리에 포함
        Node node = nodes[root]; // 노드 꺼낸 후
        
        for (Node ad : node.adjacent) {
            if (dp[ad.x] == 0) { // 처음 호출 되는 경우만 재귀적 실행  --> dp == 0
                makeSubTree(ad.x); // 인접한 노드 여기서는 자식 노드를 의미
                dp[root] += dp[ad.x]; // 자식 노드의 서브트리를 더함 
            }
        }
    }
    
    void getPrint() {
        StringBuilder sb = new StringBuilder();
        
        for (Integer q : querys) {
            sb.append(dp[q]).append("\n");
        }
        
        System.out.print(sb);
    }
    
}

2. 풀이 중점 사항

문제를 출제하신 분께서 힌트로 너무나 자세하게 잘 설명해 주셔서 추가로 설명드릴 부분은 makeSubTree를 구현한 메서드입니다.

void makeSubTree(int root) {
    dp[root] = 1; // 서브 트리에 포함
    Node node = nodes[root]; // 노드 꺼낸 후
    
    for (Node ad : node.adjacent) {
        if (dp[ad.x] == 0) { // 처음 호출 되는 경우만 재귀적 실행  --> dp == 0
            makeSubTree(ad.x); // 인접한 노드 여기서는 자식 노드를 의미
            dp[root] += dp[ad.x]; // 자식 노드의 서브트리를 더함
        }
    }
}

makeSubTree를 만드는 과정에서 각 노드는 서로 인접한 노드로 설정되어 있습니다. 따라서, 각 노드에 대한 visited를 설정해주어야 합니다. 만약 방문 여부를 설정하지 않는 다면 인접한 노드가 다시 root 노드를 호출하기 때문에 무한 루프에 빠지게 됩니다.

저는 이 과정에서 dp[i]의 값이 0이라면, 아직 재귀 호출이 되지 않은 상태 즉, 자식 노드이므로 dp[i] == 0인 경우를 visited로 대체하여 사용하였습니다.

dp를 이용하여 한 번에 서브 트리의 개수를 구할 수 있었습니다.

이상으로 백준 트리와 쿼리 자바 풀이를 마치도록 하겠습니다. 감사합니다!! 

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드 문제 - 최소 스패닝 트리 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1197

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = parseInt(st.nextToken());
        int e = parseInt(st.nextToken());
        
        Graph graph = new Graph(v); // 그래프 설정
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken()), parseInt(st.nextToken()));
        }
        
        System.out.println(graph.mst());
    }
}

class Graph {
    int n; // n개의 노드
    int[] parent; // 유니온 파인드 루트 노드
    List<Edge> edges = new ArrayList<>(); // 간선
    
    Graph(int n) {
        this.n = n;
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    
    class Edge {
        int x; // 연결된 노드
        int y; // 연결된 노드
        int w; // 가중치
        
        Edge (int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    
    void addEdge(int x, int y, int w) {
        edges.add(new Edge(x, y, w));
    }
    
    int mst() {
        int result = 0;
        edges.sort(Comparator.comparing((Edge e) -> e.w)); // 엣지 오름차순 설정

        for (Edge e : edges) {
            int p1 = find(e.x); // x의 루트 노드
            int p2 = find(e.y); // y의 루트 노드

            if (p1 == p2) continue; // 만약 두 노드의 루트 노드가 같다면 패스
            result += e.w; // 가중치 업데이트
            union(p1, p2); // 두 노드 합치기
        }
        
        return result;
    }
    
    int find(int child) { // find 경로 압축
        if (child == parent[child]) return child;
        return parent[child] = find(parent[child]);
    }
    
    void union(int p1, int p2) { // union 합치기
        parent[p2] = p1;

    }
}

2. 최소 스패닝 트리(MST)

최소 스패닝 트리를 구하는 알고리즘은 Kruskal 알고리즘이 있습니다.

Kruskal 알고리즘은 다음의 순서로 진행됩니다.

• 그래프의 모든 간선을 가중치에 따라 오름차순 정렬합니다.
• 가중치가 최소인 간선을 선택하여, 간선의 두 노드가 같은 집합에 있지 않는 경우 (루트가 다른 경우) 해당 간선에 연결된 두 노드를 하나의 집합으로 합칩니다 (유니온 파인드)
• 만약 간선이 연결하는 두 노드가 같은 집합이라면 사이클이 형성될 수 있으므로 건너뜁니다.
• 모든 간선이 검사 될 때까지 과정을 반복합니다.

        7

1 ------------- 2

                    | 

                    |  10  

                    |

                    3 -------------- 4

                              5

다음과 같은 트리가 존재한다고 가정하겠습니다.

• Kruskal 알고리즘의 순서에 따라 가중치가 가장 적은 (3, 4) 엣지, (1, 2) 엣지, (2, 3) 엣지로 정렬합니다.
• (3, 4)에 있는 노드 3, 4의 루트 노드를 검사합니다. (아직 업데이트되지 않았기에 3의 루트 노드 3, 4의 루트 노드 4)
• 두 루트 노드가 다르므로 하나로 합칩니다. 저는 x1, x2가 있을 때, x1을 루트 노드로 설정하였습니다.
• 마찬가지로 (1, 2) 엣지를 선택하여 두 노드에 대한 유니온 파인드를 진행합니다.
• 다음 엣지인 (2, 3)을 선택하여 두 노드에 대한 유니온 파인드를 진행합니다.
• 이 과정에서 분리되어 있던 두 집합 {1, 2} , {3, 4}가 하나로 합쳐지게 됩니다.
• 모든 간선에 대한 탐색을 마쳤으므로 종료합니다.

만약 해당 그래프에서 

        7

1 ------------- 2

  \                  | 

   \                 |  10  

    \                |

     \------------ 3 -------------- 4

   100                      5

1과 3을 잇는 간선이 추가될 경우 사이클을 형성할 수 있습니다.

유니온 파인드에서 두 루트 노드가 같은 경우에는 건너뛰는 이유가 바로 이러한 사이클을 방지하기 위함입니다.

이미, 간선으로 오름차순 설정하였기 때문에 후에 오는 간선은 이전에 설정한 간선보다 더 작기 때문에
그리디한 탐색 방법이 MST에서는 최적의 해를 찾을 수 있는 것입니다.

int mst() {
    int result = 0;
    edges.sort(Comparator.comparing((Edge e) -> e.w)); // 엣지 오름차순 설정

    for (Edge e : edges) {
        int p1 = find(e.x); // x의 루트 노드
        int p2 = find(e.y); // y의 루트 노드

        if (p1 == p2) continue; // 만약 두 노드의 루트 노드가 같다면 패스
        result += e.w; // 가중치 업데이트
        union(p1, p2); // 두 노드 합치기
    }
    
    return result;
}

이러한 원리를 바탕으로 소스를 보면, 먼저 엣지의 가중치를 기준으로 정렬하고,

각 간선을 탐색합니다. 엣지에 대한 노드를 유니온 파인드를 진행하고 result에 가중치를 더해줍니다

나중에는 오름차순에 따라 간선이 나오게 되며 결국 분리되어 있는 여러 개의 집합이 하나로 합쳐지기 때문에 이러한 방법을 택할 수 있습니다.

이상으로 백준 최소 스패닝 트리 자바 풀이를 마치도록 하겠습니다. 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 여행 가자 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1976

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n; // n 개의 도시
    static int m; // 들려야 하는 m개 도시
    static int[] parent; // union find
    static List<Integer> nodes = new ArrayList<>(); // 도시 번호 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        m = parseInt(br.readLine());
        
        parent = new int[n + 1]; // 초기화
        for (int i = 0; i <= n; i++) parent[i] = i; // 루트 노드 설정하기
        
        for (int row = 1; row <= n; row++) {
            // 유니온 파인드를 위해 중복되는 경로를 제거하기 위해 대각선 기준 오른쪽 탐색
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int col = 1; col <= n; col++) {
                int link = parseInt(st.nextToken());
            
                if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
                    if (link == 1) union(find(row), find(col));
                }
            }      
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) nodes.add(parseInt(st.nextToken()));
       
        boolean result = isSameRoot(); // 도시가 같은 루트를 공유하는지 판단
        System.out.println(result ? "YES" : "NO");
    }
    
    static boolean isSameRoot() {
        
        if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
        boolean check = true; // 루트가 같은지 판단
        
        int root = find(nodes.get(0));
        for (Integer node : nodes) {
            if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
                check = false;
                break;
            }
        }
        
        return check;
    }
   
    
    static int find(int x) { // find 경로 압축
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    
    static void union(int v1, int v2) {
        parent[v1] = v2;
    } // v1을 루트로 v2 합치기
}

2, 풀이 중점 사항

각 도시로 연결되는 간선은 양방향 이동 경로 입니다. 이는 곧 주어지는 n개의 줄은 대칭 형태로 주어지고 있습니다.

저는 대각선을 기준으로 오른쪽에 위치한 값으로 parent 와 child를 설정하였습니다.

col > row 인 조건에서 link == 1 이라면, row가 부모가 되어, child를 연결할 수 있도록 구성하였습니다.

if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
    if (link == 1) union(find(row), find(col));
}

이 코드의 효과로, 1 -> 2가 연결되어 있다면 root 노드가 1이 되고, 2는 루트가 1인 집합의 원소가 됩니다.

이어지는 값에서 2 -> 3으로 연결된다면, 2는 root가 1이므로 3은 root 1을 그대로 따르게 됩니다.

static boolean isSameRoot() {
    
    if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
    boolean check = true; // 루트가 같은지 판단
    
    int root = find(nodes.get(0));
    for (Integer node : nodes) {
        if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
            check = false;
            break;
        }
    }
    
    return check;
}

해당 소스에서 nodes.get(0)으로 꺼낸 root의 값이 거쳐야 하는 도시들의 root와 다르다면, 이는 다른 도시들을 경유하여 갈 수 없는 경로임을 의미하므로 false를 리턴하였습니다. 만약 거쳐야 하는 도시가 모두 root를 따른다면, 양방향 간선으로 인해, 서로 도시 간 이동이 가능합니다.

이상으로 유니온 파인드 문제 여행 가자 자바 풀이를 마치도록 하겠습니다.!

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 - 집합의 표현 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1717

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cal = parseInt(st.nextToken());
            int a = parseInt(st.nextToken());
            int b = parseInt(st.nextToken());
            
            if (cal == 0) {
                int p1 = find(a); // p1 루트 노드 찾기
                int p2 = find(b); // p2 루트 노드 찾기 
                
                union(p1, p2); // 합치기
            } else {
                boolean same = find(a) == find(b);
                sb.append(same ? "YES" : "NO").append("\n");
            }
        }
        
        System.out.print(sb);
    }
    
    static int find(int child) {

        if (child == parent[child]) return child; // 자신이 루트 노드라면
        return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
    }
    
    static void union(int p1, int p2) {
        parent[p2] = p1; // p2의 부모를 p1으로 바꾸기
    }
}

2. 풀이 중점 사항

해당 문제는 유니온 파인드를 활용하여 집합을 표현할 수 있습니다.

static int find(int child) {

    if (child == parent[child]) return child; // 자신이 루트 노드라면
    return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
}

child의 부모 노드가 자신이라면 이는 곧 루트 노드임을 의미합니다. 따라서, 자기 자신을 그대로 리턴합니다.

하지만, 만약 parent[child]가 자신이 아니라면, 루트 노드가 존재함을 의미합니다.

따라서, 경로 압축을 활용하여 find(parent[child]) 한 값을 찾아서 parent[child]에 대입하고 그 값을 리턴합니다.

예를 들어

child = 5;

parent[child] = 3;

parent[3] = 7;

parent[7] = 7 인 상황이 있습니다.

이를 경로 압축을 통해 parent를 찾으면 다음과 같습니다.

parent[5] = find(parent[5])  = find(parent[3]) = parent[7]; 이 성립되어 모두 경로를 압축할 수 있습니다.

이를 토대로 시간 복잡도를 효율적으로 개선할 수 있습니다.

이상으로 집합의 표현 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리 문제 - 트리의 지름 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/1167

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = parseInt(br.readLine());
        Graph graph = new Graph(n); // 그래프 생성
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = parseInt(st.nextToken()); // 첫 번째 문자 정점
            while (true) {
                int v2 = parseInt(st.nextToken()); // 연결할 정점 -1이면 종료
                if (v2 != -1) {
                    graph.addEdge(v1, v2, parseInt(st.nextToken())); // 간선 길이
                } else break;                 
            }            
        }
        
        graph.run(1,  0); // 임의의 정점에서 가장 긴 정점 구하기
        graph.run(graph.getNext(), 0); // 다음 정점에서 가장 긴 정점 구하기
        
        System.out.println(graph.getMax());
    }
}

class Graph {
    int n;
    int max; // 정점 최장 거리
    int next; // 다음에 dfs를 계산할 next 노드
    Node[] nodes; // 노드 배열
    boolean[] visited; // 방문 설정
    
    Graph(int n) {
        this.n = n;
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i); // 초기화
    }
    
    class Node {
        int x;
        List<Edge> edges = new ArrayList<>(); // 노드에 연결될 간선 설정
        
        Node (int x) {
            this.x = x;
        }
    }
    
    class Edge { // edge
        int y; // x 노드와 연결되는 간선 y
        int dist; // x 노드와 y 노드의 간선 길이
        
        Edge (int y, int dist) {
            this.y = y;
            this.dist = dist;
        }
    }
    
    void addEdge(int x, int y, int dist) {
        Node n1 = nodes[x];      // 단방향 간선
        n1.edges.add(new Edge(y, dist));
    }

    void run(int x, int dist) {
        visited = new boolean[n + 1]; // visited 초기화
        dfs(x, dist); // dfs 실행
    }

    void dfs(int x, int dist) {
        Node n1 = nodes[x];
        visited[n1.x] = true;

        for (Edge e : n1.edges) { // 간선 탐색
            if (!visited[e.y]) { // 간선에 연결된 노드에 방문하지 않은 경우
                dfs(e.y, dist + e.dist); // 다음 노드, 현재 거리에 간선 길이 더하기
            }
        }

        if (max < dist) { // 길이가 더 크면
            max = dist; // 길이 업데이트
            next = x; // 다음 노드 업데이트 
        }
    }
    
    int getMax() {
        return max;
    }
    int getNext() {return next;}
    
}

2. 풀이 중점 사항

트리의 지름을 구하는 알고리즘은 DFS 혹은 BFS를 두 번 탐색하여 구할 수 있습니다.

트리는 사이클이 없는 그래프이므로, 트리의 지름은 트리 상에서 가장 멀리 떨어진 두 정점의 거리입니다.

이런 특성으로 인해 한 정점에서 가장 먼 정점을 찾고 나서, 다시 그 정점에서 다시 가장 먼 정점을 찾는다면 트리의 지름을 얻을 수 있습니다.!

따라서, 두 번의 dfs를 통해 가장 긴 거리를 유지하는 정점을 찾고 다시 그 정점에서 가장 긴 정점을 찾는다면 문제를 해결할 수 있습니다.

ex)

3  - ------- - - - 1

|     \            d: 10

|      \  

|        \ d: 500

|          4

|  d: 20

2

1의 노드 입장에서 가장 먼 노드는 4번입니다. 하지만 4번 노드에서 가장 긴 정점은 2번 노드입니다.

즉 임의의 노드에서 가장 먼 노드를 찾고 그 노드에서 다시 한번 가장 먼 노드를 찾으면 트리의 지름을 구할 수 있습니다.

이상으로 트리의 지름 자바 풀이를 마치겠습니다. 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리문제 - 트리의 부모 찾기 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/11725

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        Graph graph = new Graph(n); // 그래프 생성
        
        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken())); // 간선 설정
        }
        graph.getParent();
    }
}

class Graph {
    int n; // n개 노드
    Node[] nodes; // 노드를 담을 배열
    
    Graph(int n) {
        this.n = n;
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i); // 노드 초기화
    }
    
    class Node {
        int x;
        List<Node> adjacent = new ArrayList<>(); // 인접한 노드
        
        Node (int x) {
            this.x = x;
        }
    }
    
    void addEdge(int x, int y) {
        Node n1 = nodes[x];
        Node n2 = nodes[y];
        
        n1.adjacent.add(n2); // 연결된 간선
        n2.adjacent.add(n1); // 양방향 연결
    }
    
    void getParent() {
        int[] parent = new int[n + 1]; // 부모의 노드 번호 저장
        boolean[] visited = new boolean[n + 1]; // 방문
        
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(nodes[1]);
        
        while(!queue.isEmpty()) {
            Node n1 = queue.poll();
            
            visited[n1.x] = true;
            
            for (Node ad : n1.adjacent) {
                if (!visited[ad.x]) { // 아직 방문하지 않았다면 큐의 성질로 부모의 자식 노드 반환
                    queue.add(ad); // 큐에 추가 
                    parent[ad.x] = n1.x; // 자식 노드 번호에 부모 노드 번호 저장
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 2; i <= n; i++) sb.append(parent[i]).append("\n");
        
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

부모 노드의 인접한 노드는 자식 노드입니다. 큐의 성질을 활용하여 루트 노드를 큐에 넣고, 큐에 있는 인접한 노드 (자식 노드)를 큐에 넣습니다. 각 노드를 방문할 때마다 방문 처리하여, 다른 인접한 노드의 호출로 노드가 두 번 이상 큐에 들어가지 않도록 설정합니다. 이러한 방법으로 자식 노드의 부모 노드 번호를 출력할 수 있습니다. 자세한 풀이는 주석화 하였습니다.

이상으로 백준 트리 문제 트리의 부모 찾기 풀이를 마치도록 하겠습니다. 

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 벽장문의 이동 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2666

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main{
    static int n, m;
    static int[] arr;
    static int[][][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int left = parseInt(st.nextToken()); // 왼쪽에 있는 포인터
        int right = parseInt(st.nextToken()); // 오른쪽에 있는 포인터
        
        m = parseInt(br.readLine());
        // dp[m][n][n] => m번째 움직어야 하는 방을 움직일 때, left와 right의 움직임 최소 값
        dp = new int[m][n + 1][n + 1]; // m은 이동 해야하는 개수, n + 1 : left 이동, n + 1: right 이동
        arr = new int[m]; // 움직어야 하는 방 저장
        for (int i = 0; i < m; i++) arr[i] = parseInt(br.readLine());
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) // (n은 1부터)
                Arrays.fill(dp[i][j], -1); // 초기 값은 -1로 초기화
        }
        
        System.out.println(dfs(0, left, right));
    }
    
    static int dfs(int idx, int left, int right) {
        if (idx == m) return 0; // 움직여야 하는 모든 움직임을 마친 경우
        
        if (dp[idx][left][right] == -1) { // 아직 dp가 업데이트 되지 않았음
            dp[idx][left][right] = Math.min(
                Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right), // left가 움직인 값 + 재귀로 다음 항, left가 움직여진 위치, right
                Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
            );
        }
        return dp[idx][left][right];
    }
}

2. 풀이 중점 사항

점화식 세우기

dp[m][left][right] 는 m번째 자리에 있는 방의 번호를 옮기는데 left방이 총 이동한 거리와 right 방이 총 이동한 거리를 더한 값의 최소를 DP로 정의하였습니다.

즉, 만약 m = 2, left = 3, right = 4라면, 현재 m의 방에서 left가 3에 위치해 있고 right가 4에 위치해 있는 상태까지 총거리의 최소를 의미하게 됩니다.

dp[idx][left][right] = Math.min(
	Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right),
    Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
)

이 점화식은 left - arr[idx] 즉 idx 번째에 옮겨야 하는 방의 위치에서 left를 뺀 후 절댓값을 취한 것이므로 이동 거리를 의미합니다.

그리고 arr[idx]는 현재 left를 움직였으므로 그 위치의 값을 넣어준 것입니다.

시나리오 

방 6개

m = 2

arr = {1, 4} 

left = 2, right  = 5 가 주어져 있다고 생각하겠습니다.

dp[0][2][5] = Math.min(

    Math.abs(left - arr[0]) + dfs(1, 1, 5)

    = Math.abs(2 - 1) + dfs(1, 1, 5)  = 1 +  dfs(1, 1, 5)

    = 1 + 

              dp[1][1][5] = Math.min(

                  Math.abs(1 - arr[1]) + dfs(2, arr[1], 5) 

                  = Math.abs(1 - 4) + dfs(2, arr[1], 5) 

                  = 3 + dfs(2, 4, 5)

                  = 3 

                 , 

                 Math.abs(5 - arr[5]) + dfs(2, 1, arr[5])

                 = 1 + dfs(2, 1, 4)              

                 = 1 

                )

            =  1

            (dp[1][1][5] = 1 저장)

  = 1 + 1 = 2  

   , Math.abs(right - arr[0]) + dfs (1, 2, 1)

     = Math.abs(5 - 1) + dfs(1, 2, 1)

     =   4 + dfs(1, 2,  1) ~ 

이와 같은 재귀 형태로 반복이 진행됩니다.

따라서, 최솟값을 DFS 형태와 dp를 활용하여 구할 수 있습니다.

이상으로 벽장문의 이동 자바 풀이를 마치도록 하겠습니다. 감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 DP 계단 수 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1562

1. 풀이 소스

import java.io.*;

public class Main {
    static final int MOD = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110
        for (int i = 1; i <= 9; i++) 
            dp[1][i][1 << i] = 1; // 1자리에서 k라는 수가 오는 경우 (0은 첫번째 자리에 올 수 없음)
        
        for (int t = 2; t <= n; t++) {
            for (int k = 0; k <= 9; k++) { // 2자리부터는 0 가능
                for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
                    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)
                    
                    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
                    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
                    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능
                
                    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
                }
            }
        }
        
        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i][(1 << 10) - 1] % MOD; // 비트마스크의 마지막인덱스 1 111 111 111 (모든 숫자 방문)
            sum %= MOD;
        }
        
        System.out.println(sum);
    }
}

2. 풀이 중점 사항

계단 수

계단 수의 DP 점화식은 다음과 같습니다.

dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k + 1] // n은 자리수, k는 n의 자리에 있는 숫자

예를 들어 xx7이 있다고 가정하겠습니다.

xx7은 두번째 자리 수(3 - 1)가 6(k - 1) 이거나 8(k + 1) 인 값이어야 합니다.   

x67은 첫번째 자리수가 (2 - 1)가 5(k - 1) 이거나 7(k + 1)인 값이어야 합니다.

즉, 현재 n 번째 자리에서 k라는 숫자가 오기 위해서는 n - 1 자리에서 k - 1 숫자가 있는 dp와 n - 1 자리에서 k + 1 숫자가 있는 dp를 더해야 합니다.

하지만, 0 과 9의 경우는 0은 올라가는 계단 수만, 9는 내려가는 계단 수만 존재하므로  하단의 점화식을 세울 수 있습니다.

if (k == 0) dp[t][k] += dp[t - 1][k + 1]; // k == 0 인 경우 올라가는 연산만 존재
else if (k == 9) dp[t][k] += dp[t - 1][k - 1]; // k == 9인경우 내려가는 연산만 존재
else dp[t][k] += dp[t - 1][k + 1] + dp[t - 1][k - 1]; // 둘 다 가능

비트 마스킹 

다음은 0 ~ 9 까지 모든 숫자가 등장하는 계단 수를 구해야 합니다.

이를 위해 비트마스킹을 활용할 수 있습니다.

비트마스킹은 이전 풀이에서 활용한 방법으로 1 ~ n까지 숫자가 있을 때 방문 처리를 비트형태로 표현하는 방법입니다.

1 << 3 을 쉬프트 하게되면  1000 이 나오는데, 0은 방문 X, 1은 방문 O을 의미하도록 할 수 있습니다.

가령 111은 1, 2, 3번을 모두 방문 했다는 의미로 해석할 수 있습니다.

long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110

따라서, 기존의 점화식에 비트마스킹으로 방문 처리를 하는 기능을 추가하였습니다.

for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)

    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능

    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
}

이후, nextVisited  = visited | (1 << k)의 비트 or 연산으로 방문 처리가 될 수 있도록 하였습니다.

1000  | 0100   => 1100 이므로 (1, 2 번 방문)

만약 visited = 111 111 111 이었고, k == 9여서

nextVisited = 111 111 111 | 1 000 000 000 => 1 111 111 111이 된다면,
이는 곧  모든 위치를 방문한 경우를 의미하게 됩니다.

이상으로 계단 수 자바 풀이를 마치도록 하겠습니다. !

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 공통 부분 문자열 자바 풀이를 진행하고자 합니다.

문제 출처 https://www.acmicpc.net/problem/5582

1. 풀이 소스 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str1 = br.readLine(); // 입력 받을 문자열
        String str2 = br.readLine(); // 입력 받을 문자열
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; // 길이 + 1 길이 + 1 로 선언
        
        int max = 0;
        
        // row, col 을 1부터 시작하는 이유는 인덱스 에러 방지 
        for (int row = 1; row <= str1.length(); row++) {
            for (int col = 1; col <= str2.length(); col++) {
                if (str1.charAt(row - 1) == str2.charAt(col - 1)) { // 문자열은 0부터 시작하므로 실제 row = 1에 해당하는 문자는 0 
                    dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)
                    max = Math.max(max, dp[row][col]);
                }
            }
        }
        System.out.println(max);
    }
}

2. 풀이 중점 사항

해당 문제는 연속된 부분 문자열의 가장 큰 크기를 구해야 하는 것이 목표였습니다.

str1: ACABACD 

str2: ABABC

라는 문자열이 주어졌을 때, 두 문자열의 가장 긴 부분 문자열을 구하는 것은 다음의 표와 같습니다.

행의 첫번째 열은 str1의 문자 인덱스 번호이고, 열의 첫 번째 행은 str2의 인덱스 번호입니다.

(2, 0), (3, 1), (4, 2)의 문자열은 

str1의 ABA,  str2의 ABA입니다. 

이는 곧, 만약 B = B라면, 앞에 row - 1, col - 1의 값에 + 1을 하는 것과 동일하게 됩니다.

왜냐하면, B = B라면 앞에 같은 연속된 문자열이 있을 수도 있는데, 그 값을 DP가 저장하고 있기 때문입니다.

따라서, DP는 현재 주어진 문자열 A의 인덱스와 비교하고자 하는 문자열 B의 인덱스에 있는 문자가 같다면 
이전 연속된 값이 있는지 DP에서 확인하여 +1을 하는 로직을 구할 수 있습니다.

dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)

따라서, 이와 같은 로직을 구할 수 있게 되는 것 입니다.

이상으로 백준 DP 공통 부분 문자열 풀이를 마치도록 하겠습니다.

감사합니다!!!