[JAVA] 백준 4933 뉴턴의 사과

문제 : https://www.acmicpc.net/problem/4933

 

혹시 문제를 풀기 전에 모호한 부분이 많아서 시도를 못하신 분들은 아래 글을 읽어 보고 다시 도전해 보세요!

 

+ 문제 부연 설명

 

"두 트리가 같다"에 대해

  - '두 트리가 같다'는 부모 내 자식들의 자리를 바꿔서 같은 트리가 된다면 같은 트리입니다. 

 

-  구조는 같지만 같은 위치의 정점 이름(A, B..) 이 다른 경우에 대해서는 과감하게 같지 않은 트리라고 생각하셔도 됩니다.

 

입력 범위에 대해.

  - 모든 채점 결과에 대해(지금 기준)  "시간초과"가 나온 적이 없는 문제입니다. 크게 신경 쓰지 않으셔도 됩니다. 

---

혹시 저만 모호하다고 생각했나요..? 그럼 이제 문제를 풀어보겠습니다.

 

문제를 정리해 보자면 입력받은 값으로 트리 구조를 만들어 두 트리가 같은지 (문제에서 정의한) 확인해야 합니다. 

 

입력으로 들어오는 값은 PostOrder로 들어옵니다. 

 

우선 입력이 왜 저따구로 들어오는지 알아야 합니다. PostOrder는 맨 마지막에 root 노드가 오니까 역순으로 읽어보면 입력의 구조에 대해 좀 더 쉽게 이해할 수 있습니다. 

 

입력 값을 역순으로 나열해서 읽어주세요.

 

 그럼 이제 이 입력 값을 토대로 트리 구조를 만들어야 합니다. 

 

입력 값의 구조를 좀 고민하다 보면

이해..해주세요

 

위와 같은 구조를 발견할 수 있습니다. 이를 글로 좀 더 명확하게 표현해 보자면 

 

노드 A의 자식 노드 B에 대해 B가 nil이 아니라면 A의 다른 자식노드 F 사이에 B의.. 잠시 타임. 다시 할게요.

 

for( 2번)

   childNode = stack.pop()

   if not nil

   findChild(childNode)

 

혹시 이걸로 설명을 대체해도 될까요? 아무튼 재귀 호출을 통해 트리 구조를 만들 수 있습니다.

 

저는 HashMap <String, List <String>>에 넣어서 2개의 map을 만들어서 비교를 하였습니다. 

 

코드

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

public class Num4993_뉴턴의사과 {
    static int testCase;
    static boolean isSame;
    static Stack<String> stack1,stack2;
    static HashMap<String, List<String>> map1,map2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        for(int i=0;i<testCase;i++){
            stack1 = new Stack<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (true){
                String input = st.nextToken();
                if(input.equals("end")) break;
                stack1.add(input);
                if(input.equals("nil")) continue;
                map1.put(input, new ArrayList<>());
            }
            st = new StringTokenizer(br.readLine());
            stack2 = new Stack<>();
            while (true){
                String input = st.nextToken();
                if(input.equals("end")) break;
                stack2.add(input);
                if(input.equals("nil")) continue;
                map2.put(input, new ArrayList<>());
            }
            // 빈 트리
            if(stack1.isEmpty() && stack2.isEmpty()){
                sb.append(true).append("\n");
                continue;
            }else if(stack1.isEmpty() || stack2.isEmpty()){
                sb.append(false).append("\n");
                continue;
            }
            String root1 = stack1.pop();
            findSubTree(root1,map1,stack1);
            String root2 = stack2.pop();
            findSubTree(root2,map2,stack2);

            isSame = compareTree(root1,root2);
            sb.append(isSame).append("\n");
        }
        System.out.print(sb);
    }
    public static void findSubTree(String now,HashMap<String,List<String>> map,Stack<String> stack){
        for(int i=0;i<2;i++){
            if(stack.isEmpty()) return;
            String tmp = stack.pop();
            if(tmp.equals("nil")){
                continue;
            }
            map.get(now).add(tmp);
            findSubTree(tmp,map,stack);
        }
    }
    public static boolean compareTree(String root1, String root2){
        if(!root1.equals(root2)) return false;
        if(map1.get(root1).size() == map2.get(root2).size()){
            List<String> list1 = map1.get(root1);
            List<String> list2 = map2.get(root2);
            Collections.sort(list1);
            Collections.sort(list2);
            for(int i=0;i<list1.size();i++){
                if(!compareTree(list1.get(i),list2.get(i))) return false;
            }
        }else{
            return false;
        }
        return true;
    }
}

 

후기

map을 하나만 사용하여 시도해 봤는데, 실패했어요ㅠ

처음 입력만 트리 구조를 만든 다음 두 번째 입력에서는 기존의 구조와 비교하여 문제를 풀어봤는데 틀리더라고요. 

 public static void findSubTree2(String now){
        if(!isSame) return;
        if(stack.isEmpty()) return;
        for(int i=0;i<2;i++){
            String tmp = stack.pop();
            if(tmp.equals("nil")){
                continue;
            }
            if(!map.get(now).contains(tmp)) isSame = false;
            findSubTree2(tmp);
        }
    }

 

틀린 이유를 정말 모르겠어요.