[백준] 14725 개미굴 (Python)

14725번: 개미굴

문제

문제

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한 마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

예제 입력 1 복사

3
2 B A
4 A B C D
2 A C

예제 출력 1 복사

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

예제 입력 2 복사

4
2 KIWI BANANA
2 KIWI APPLE
2 APPLE APPLE
3 APPLE BANANA KIWI

예제 출력 2 복사

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

---

문제 풀이

 

겹치는 문자열을 처리해야 하는 문제이다.

 

이 문제를 접근할 때, 층별로 겹치는 부분은 추가로 출력하지 않아야 하고, 입력값을 받아올 때부터 데이터 처리를 할 수 있으면 좋겠다고 생각했다.

 

그래서 생각한 방법이 dictionary를 사용하는 것이다.

 

구조는 다음과 같다.

food_dict의 key값들은 해당 층에 존재하는 음식,

 value 값들은 해당 음식 아래층에 존재하는 음식들 (dictionary)

따라서 dictionary들이 여러개 중첩되어 있는 형태.

 

예제 입력 1을 예로 들면

#--입력--#
3
2 B A
4 A B C D
2 A C
#--print(dict_foods) 결과--#
{'B': {'A': {}}, 'A': {'B': {'C': {'D': {}}}, 'C': {}}}

 

저장 방식은 다음과 같다.

dictionary를 확인

해당 층에 확인하고자 하는 음식이 존재할 경우,

-- 다음 층으로 내려간다.

존재하지 않는 경우,

-- 해당 층에 음식을 생성 후 다음 층으로 내려간다.

입력 foods의 개수만큼 반복한다.

(여기서 다음 층은 해당 음식을 통해 만날 수 있는 음식들의 dictionary)

 

저장은 문제없이 진행되었으나 출력에서 구조적인 문제점이 발생하게 된다.

 

dictionary는 사전순서대로 key를 정렬할 수 없다는 점.

 

그래서 list로 변경하여 key값들을 정렬한 뒤,

해당 list를 이용하여 dictionary를 접근하는 방식을 사용했다.

 

 

 

---

코드

 

###### 출력하는 함수 #######

def food_printer(dict_foods,layer):
    list_foods = sorted(list(dict_foods))		# 사전순으로 접근해야 하므로 dict_foods의 key들을 리스트로 만들어 정렬
    for i in list_foods:
        print("--"*layer,end="")
        print(i)
        food_printer(dict_foods[i],layer+1)		# 재귀 형식으로 재접근


###### 입력과 데이터 처리 ######
N = int(input())
dict_foods = dict()
for i in range(N):
    K,*foods = input().split()		#처음 들어오는 수를 제외한 나머지가 음식들

    layer = dict_foods		#계속해서 내려가야 하기 때문에 tmp에 해당 dictionary를 부여하여 접근할 수 있도록 함
    for food in foods:	#들어온 음식의 순서대로 확인
        if food not in layer:	# 존재하지 않는다는 뜻이기 때문에 해당 음식을 key로 하여 새로운 dictionary 생성
            layer[food] = dict()	
        layer = layer[food]		#다음 층으로 진행

food_printer(dict_foods,0)

 

---