[알고리즘]2233_사과나무

백준_2233

• 벌레들 루트에서 DFS로 탐색, 오른쪽 먼저 방문.

• 새로운 노드 방문 시 0, 모든 자식노드 방문 후 리턴할 때 1. 나열한 하나의 이진 수열.

• 한번만 가지쳐서 썩은 사과 제거, 멀쩡한 사과 최소로 -> 가장 가까운 공통부모 찾기

• 그럼 이진 수열을 트리로 만들고 썩은 사과들의 노드에 가장 가까운 공통 부모노드

  • 그냥 이진수의 0값 인덱스를 부모노드 인덱스로 생각하면 되겠다는 생각

  • 괄호 닫기 느낌으로 스택으로 트리 만들기

• x랑 y가 0값 인덱스인지 1값 인덱스인지 모르니까 0값으로 변환, 통일

• 그리고 공통부모도 0값 인덱스랑 1값 인덱스 반환 필요

  • 두 배열 만들어서 각각 저장. 변환용

• 공통부모는 같은 depth로 맞추고 값 같아질때까지, 이후 같은 높이일 때 같은 노드인 경우 나올때까지 부모로 감. 같을 때 최소 공통 부모

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

public class Main {

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

        int N = Integer.parseInt(br.readLine()); // 정점 개수

        // 0,1 이진 수열 (길이 = 2N)
        String bin = br.readLine().trim();
        int M = bin.length(); // 실제 이진수 길이

        // x, y 위치. 시작 인덱스 0으로 설정
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken()) - 1;
        int y = Integer.parseInt(st.nextToken()) - 1;

        // 0 인덱스 -> 짝이 되는 1 의 인덱스
        int[] zeroToOne = new int[M];
        // 1 인덱스 -> 짝이 되는 0의 인덱스
        int[] oneToZero = new int[M];
        Arrays.fill(zeroToOne, -1);
        Arrays.fill(oneToZero, -1);

        // 각 0 위치의 부모 0 위치 인덱스
        int[] parent = new int[M];
        // 공통 부모 찾기용
        int[] depth = new int[M];
        Arrays.fill(parent, -1);

        Deque<Integer> stack = new ArrayDeque<>();

        // 0/1 수열에서 부모 설정
        for (int i = 0; i < M; i++) {
            char c = bin.charAt(i);

            if (c == '0') {
                // parent / depth 설정
                if (stack.isEmpty()) {
                    // 루트
                    parent[i] = i;   // 루트는 자기 자신을 부모로
                    depth[i] = 0;
                } else {
                    parent[i] = stack.peekLast();          // 스택 top이 부모 노드의 0 위치
                    depth[i] = depth[parent[i]] + 1;
                }
                stack.offerLast(i);
            } else {
                int openIdx = stack.pollLast();
                zeroToOne[openIdx] = i;  // 이 0의 닫힘 위치는 i
                oneToZero[i] = openIdx;  // 이 1의 여는 위치는 openIdx
            }
        }



        // 주어진 x, y 인덱스를 해당 노드의 0 위치로 변환
        int u = (bin.charAt(x) == '0') ? x : oneToZero[x];
        int v = (bin.charAt(y) == '0') ? y : oneToZero[y];

        // 가장 가까운 공통 부모 찾기
        int lca = lca(u, v, parent, depth);

        int ZeroPos = lca;               // 이 부모의 0 위치
        int OnePos = zeroToOne[lca];   // 이 부모의 1 위치

        // 시작위치 1로 수정
        System.out.println((ZeroPos + 1) + " " + (OnePos + 1));
    }

    // 가장 가까운 공통 부모 찾기
    private static int lca(int a, int b, int[] parent, int[] depth) {
        while (depth[a] > depth[b]) {
            a = parent[a];
        }
        while (depth[b] > depth[a]) {
            b = parent[b];
        }

        while (a != b) {
            a = parent[a];
            b = parent[b];
        }
        return a;
    }
}