[백준] 알고리즘 분류(트리,JAVA)14725번, 개미굴

문제 링크

14725번: 개미굴

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 개미굴의 각 층을 "--"으로 구분하며 같은 층에 여러 방 있을 때 사전 순으로 출력됩니다.

2. 입력된 정보을 토대로 각 층의 존재하는 방들을 저장해야합니다.

3. 개미굴의 시각화된 구조를 결과로 출력해야합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 트리의 탐색 정보를 저장합니다.

 

2. 탐색 정보를 가지고 각 층의 존재하는 방들을 구성합니다.

 

3. 구성한 개미굴을 시각화된 구조로 출력합니다.

 

개미굴 각 층 구성하기.

 

각 층의 방에 연결된 아래 층의 방들을 저장하도록 하는 트리 형태로 구성하게 하였습니다.

 

HashMap<String , node>의 형태로 반복하여 Root가 되는 방부터 하위 구조가 만들어지도록 하였습니다.

 

문제에서 그림으로 설명하는 개미굴을 표현해보면

1층

Root : HashMap<String , node> : "APPLE", "KIWI"

 

2층

"APPLE" : HashMap<String, node> : "APPLE", BANANA"

"KIWI" : HashMap<String, node> : "APPLE", "BANANA"

 

3층

"APPLE" : HashMap<String, node> : Empty

"BNANA" : HashMap<String, node> : "KIWI"

 

"APPLE" : HashMap<String, node> : Empty

"KIWI" : HashMap<String, node> : Empty

 

4층

"KIWI" : HashMap<String, node> : Empty

 

 

 

시각화된 구조 만들기

 

각 층의 방들을 모두 List에 저장한 뒤

사전 순으로 정렬하여 가장 우선인 방부터 아래층으로 탐색하는 것을 반복합니다.

 

층을 내려갈 때에는  "--"을 추가해서 각 층에 대해서 표현하도록 합니다.

 

 

 

예제입력 1.

 

1. 입력된 트리의 탐색 정보를 저장합니다.

※루트 노드를 1번으로 하는 이유는 모든 테스트에 항상 존재하기 때문입니다.

 

N : 3

 

2 B A
4 A B C D
2 A C

 

 

 

2. 탐색 정보를 가지고 각 층의 존재하는 방들을 구성합니다.

 

1층

Root : HashMap<String , node> : "B", "A"

 

2층

"B" : HashMap<String, node> : "A"

"A" : HashMap<String, node> : "B", "C"

 

3층

"A" : HashMap<String, node> : Empty

 

"B" : HashMap<String, node> : "C"

"C" : HashMap<String, node> : Empty

 

"C" : HashMap<String, node> : "D"

 

4층

"D" : HashMap<String, node> : Empty

 

 

3. 구성한 개미굴을 시각화된 구조로 출력합니다.

 

1층

"B"와 "A"에서 사전이 더 빠른 "A"방부터 표시 후 탐색

 

2층("--" )

"A"에 속한 "B", "C"에서 사전이 더 빠른 "B"방 표시 후 탐색

 

3층("----")

"B"에 속한 "C" 표시 후 탐색

 

4층("-------")

"C"에 속한 "D" 표시

 

2층("--")

"A"에 속한 "B", "C" 중 남은 "C" 표시

 

1층

남은 "B" 방 표시 후 탐색

 

2층("--" )

"B"에 속한 "A" 표시

 

A
--B
----C
------D
--C
B
--A

을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리 탐색의 정보를 띄어쓰기 기준 나누었습니다.
• 입력되는 탐색 정보를 통해서 Root부터 자식 구조를 형성합니다.
• 형성된 구조로 개미굴을 시각화한 구조로 만드는 print함수를 실행합니다.
• 시각화한 구조를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• print함수는 각 자식 구조에 대하여 List에 저장한 뒤 Collections.sort를 이용하여 정렬합니다.
• print함수는 재귀를 통해 개미굴을 조건대로 방문한 방을 StringBuilder에 저장합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main{
    //트리 정보 관련 클래스
    static class node{
        HashMap<String, node> child;
        public node(){
            child = new HashMap<>();
        }
    }
    static int N;
    static node root = new node();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        //개미굴 구조 만들기
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int K = Integer.parseInt(st.nextToken());
            node cur = root;
            for(int j=0;j<K;j++){
                String temp = st.nextToken();
                if(!cur.child.containsKey(temp)){
                    cur.child.put(temp, new node());
                }
                cur = cur.child.get(temp);
            }
        }
        //개미굴에 시각화시키기
        print(root, "");
        bw.write(sb +"");	//시각화한 결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //개미굴 시각화한 구조 만드는 함수
    static void print(node cur, String s){
        //현재 방에 자식 구조 가져오기
        ArrayList<String> list = new ArrayList<>(cur.child.keySet());
        Collections.sort(list);		//사전 순 정렬
        //정렬 이후 사전 순으로 표시 후 탐색
        for(String str : list){
            sb.append(s).append(str).append("\n");
            print(cur.child.get(str), s +"--");
        }
    }
}