백준 14725 (개미굴)

문제

---

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

 

 

 

 

 

풀이

---

하나의 클레스를 만들어서 풀었다.

static class house implements Comparable<house>{
		
	public List<house> child;		
	public String food;
	
	public house(String food) {
		this.food = food;
		child = new ArrayList<house>();
	}
	@Override
	public int compareTo(house h) {
		// TODO Auto-generated method stub
		
		return this.food.compareTo(h.food);
	}
}

 

자식이 여러개 있을 경우 사전순으로 정렬하기 위해 implements Comparable을 추가해주었다.

 

자식이 추가됐을 때 그 자식이 있는지를 확인하여 있을 경우는 해당 위치의 자식에 넣어주기 위해 찾아주는 코드다.

static int findChild(List<house> list, String food) {
		
	int index  = -1;
		
	for(int i = 0 ; i < list.size(); i++) {
		if(list.get(i).food.equals(food)) {
			index = i;
			break;
		}
	}
	
	return index;
}

 

답을 출력하는 과정은 DFS(깊이우선탐색)을 사용하였다.

static void dfs(List<house> list, String depth) {
		
		
	for(int i = 0 ; i < list.size() ; i++) {
		house now = list.get(i);
		sb.append(depth + now.food + "\n");
		if(now.child.size() != 0) {
			dfs(now.child, "--" + depth);
		}
	}
}

해당 집의 위치에 자식이 있으면 dfs 를 하여준다. 이때 깊이가 깊어지면 "--" 를 추가해주어양하니까 이때의 String은 "--"를 추가한다.

 

 

<전체코드> 

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class house implements Comparable<house>{
		
		public List<house> child;		
		public String food;
		
		public house(String food) {
			this.food = food;
			child = new ArrayList<house>();
		}

		@Override
		public int compareTo(house h) {
			// TODO Auto-generated method stub
			
			return this.food.compareTo(h.food);
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		house enter = new house(null);
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			int k = Integer.parseInt(st.nextToken());
			
			List<house> list = enter.child;
			for(int j = 0 ; j < k ; j++) {
				String food = st.nextToken();
				int idx = findChild(list, food);
				if(idx == -1) {
					house newFood = new house(food);
					list.add(newFood);
					list = newFood.child;
				}
				else {
					list = list.get(idx).child;
				}
			}
		}
		
		sort(enter.child);
		
		dfs(enter.child, "");
		
		System.out.println(sb);
	}
	
	static void sort(List<house> list) {
		
		Collections.sort(list);
		
		for(int i = 0 ; i < list.size(); i++) {
			if(list.get(i).child.size() != 0) {
				sort(list.get(i).child);
			}
		}
	}
	
	static int findChild(List<house> list, String food) {
		
		int index  = -1;
		
		for(int i = 0 ; i < list.size(); i++) {
			if(list.get(i).food.equals(food)) {
				index = i;
				break;
			}
		}
		
		return index;
	}
	
	static void dfs(List<house> list, String depth) {
		
		
		for(int i = 0 ; i < list.size() ; i++) {
			house now = list.get(i);
			sb.append(depth + now.food + "\n");
			if(now.child.size() != 0) {
				dfs(now.child, "--" + depth);
			}
		}
	}
}