[백준] 14725 개미굴

1. 문제

www.acmicpc.net/problem/14725

14725번: 개미굴

2. 접근방법

Map 과 key 정렬 재귀를 잘 섞어놓은 문제

 

우선 로봇개미는 자신이 정한 리프노드까지 쭉 들어간다고 하였다.

 

그러니 로봇개미가 보내는 신호는 항상 층 순서대로 나오게 된다.

 

그러면 나오는 순서대로 부모 - 자식 잘 매핑 시켜서 저장하면 되는데

자식 역시 부모가 될 수 있다.

 

그래서 Key Value 형태의 Map을 사용해

Key에는 해당노드의 이름이 Value에는 그 노드의 자식들을 또 Map을 이용해 저장했다.

 

 

map은 루트노드

코드로 보면

target이라는 껍데기를 두고

처음에 이 껍데기에 1층들을 저장한 map을 넣는다.

 

개미가 맨 처음 만난 노드 (1층)의 값을 target에 저장하는데

이미 저장이 한번이라도 됐다면 패쓰

 

그 다음 방금 저장한 노드 밑의 2층을 볼거니

target을 해당 이름 밑의 map으로 바꾸고

다시 반복 한다.

 

이런 식으로 모든 값을 저장시키면 부모 - 자식 관계를 잘 맞추어 저장이 가능하다.

 

그 다음

이 저장된 관계를 문제에서 요구하는데로 잘 출력해야 하는데

나는 재귀를 이용하였다. (dfs) 

 

먼저 루트부터 시작해서

map을 키 기준으로 정렬을 시키고 ( 나는 TreeMap을 이용해서 자동으로 정렬이 되어져있다.)

정렬된 노드를 하나 꺼내

해당 노드의 깊이만큼 -- 를 추가하고

그 노드의 이름을 추가 한뒤

 

그 노드의 자식 노드들을 보러 들어간다.

자식노드들도 똑같이 다 보고 나면

 

그 다음 노드의 자식들을 또 끝까지 보러 간다.

 

즉 dfs를 활용해 모든 노드를 지나다니면서 출력시키는 것이다.

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class G2_14725개미굴 {
	static StringBuilder result = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N;
		TreeMap<String, TreeMap > map = new TreeMap<>();
		N = Integer.parseInt(st.nextToken());
		
		for(int i = 0 ; i< N ; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			TreeMap target = map;
			for(int j = 0 ; j < n ; j++) {
				String name = st.nextToken();
				if(target.get(name) == null)
					target.put(name, new TreeMap<>());
				target = (TreeMap)target.get(name);
			}
		}
		getresult(map,0);
		System.out.println(result);
	}
	static void getresult(TreeMap map,int n) {
		
		for(Object s : map.keySet()) {
			for(int i = 0 ; i < n ; i++)
				result.append("--");
			result.append(s + "\n");
			getresult((TreeMap)map.get(s),n+1);
		}
	}

}

4. 파이썬 코드

N = int(input())
dict = {}
for i in range(N):
    inputarr = list(input().split())
    target_dict = dict
    for j in inputarr[1:]:
        if j not in target_dict:
            target_dict[j] = {}
        target_dict = target_dict[j]

def getresult(target, n):
    target_key = sorted(target.keys())
    for s in target_key :
        print('--'*n+s)
        getresult(target[s],n+1)

getresult(dict,0)

 

5. 마치며

트리 구조에 대한 이해와

dfs에 대해서 알고 있다면 어렵지 않게 해결 가능한 문제