BAEKJOON #14725 개미굴 - (문자열, DataStructure) - python

nathan·2021년 11월 17일
0

알고리즘문제

목록 보기
89/102

개미굴

출처 : 백준 #14725

시간 제한메모리 제한
1초256MB

문제

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

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

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

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

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

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

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

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

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

  • 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


풀이

생각

  • 위 이미지와 같이 굴 하나하나를 노드로 생각하여 next 정보를 담게 하면 된다고 생각했다.
  • 클래스로 노드를 구현하여 vertex, next에 대한 정보를 담았다.
  • 그리고 burrow에 시작 노드들을 담은 뒤 dfs를 통해 순차적으로 정보를 담을 수 있도록 하였다.
    • 정보를 순차적으로 담을 때 depth에 따라서 '--'가 depth에 비례하여 증가하게끔 담았다.
    • 이때 depth를 가장 첫 번째 원소로 배치하여 클수록 원소가 앞에 오게끔 했고, 이를 통해 dfs를 구현할 수 있었다.
    • heap 자료구조를 쓰지 못한 이유는 node 정보간에 비교가 되지 않기 때문이다.
    • 따라서 deque 자료구조를 활용하여 while문을 돌 때마다 update해주었다. (사실상 maxHeap 구현)

어려웠던 점

  • 사실 구현도 그렇게 쉽다고 할 수는 없겠으나, 사전순으로 나열하는 것이 곤욕스러웠다. 이유는 node라는 클래스로 정보가 리스트에 들어가게 되는데, 이는 객체로 인식이 되기 때문에 이를 통해서는 사전 순 나열이 힘들었기 때문이다.
  • 따라서 sorted를 통해 구현하고자 하였다.
  • 핵심은 sorted 내의 key=lambda x: x.vertex이다.
    • 이를 통해 객체로써 비교하는 것이 아닌 vertex 정보로 사전 순 나열이 가능케 되었다.

python code

# 백준 14725번 개미굴
from sys import stdin
from collections import deque
from heapq import heappush, heappop, heapify
input = stdin.readline
n = int(input())

class Node:                     # 개미굴에 대한 정보를 담는 노드
    def __init__(self, vertex):
        self.vertex = vertex    # 노드 내용
        self.next = []          # 다음 노드들을 담는 리스트

burrow = [] # 시작 노드들을 담을 리스트

for i in range(n):
    # temp = arr[i]
    temp = list(map(str, input().rstrip().split()))
    nunmber = int(temp[0])
    temp = temp[1:]
    
    f = False                       # burrow에 있는지 여부를 체크
    now = Node(temp[0])             # 시작 노드를 생성    
    for b in burrow:                
        if now.vertex == b.vertex:  # burrow에 있다면
            f = True                # 체크 해주고
            now = b                 # now를 해당 노드로 교체 해준다.(이 부분이 없으면 새로운 클래스로 인식하여 중복 값이 들어가게 됨)
            break
    if not f:   # burrow에 없으면,,
        burrow.append(now)          # 추가해준다.
    for t in range(1, len(temp)):
        new_node = Node(temp[t])    # start의 다음 노드부터 시작!  
        if len(now.next) == 0:      # next 노드에 아무것도 없다면
            now.next.append(new_node)   # new_node를 next에 추가!
            flag = True             # new_node가 추가되었다는 sign
        else:
            flag = False            # 아직 new_node가 append되지 않음
            for n in now.next:      
                if n.vertex == new_node.vertex:
                    new_node = n    # node update (중복 방지)
                    flag = True     
                    
        if not flag:  # 존재하지 않을 때:       
            now.next.append(new_node)
            # next 노드 내에서 사전 순으로 정렬될 수 있도록 해주기
            now.next = list(sorted(now.next, key=lambda x : x.vertex))
        now = new_node  # now 를 next 로 업데이트
        
def dfs(node):
    temp = []
    depth = 0
    maxHeap = deque([(depth, node)])
    while maxHeap:
        depth, node = maxHeap.popleft()
        temp.append("--" * depth + node.vertex)
        for next_node in node.next:
            maxHeap.append(((depth+1), next_node))
        maxHeap = deque(list(sorted(maxHeap, key = lambda x : x[0], reverse=True)))
    return temp

result = []
for b in burrow:
    temp = dfs(b)
    result.append(temp)

# 시작 노드들이 사전순으로 정렬될 수 있도록 해주기(result 원소 내 리스트 중 첫 번째가 시작 노드)
result = list(sorted(result, key = lambda x : x[0]))

for re in result:
    for r in re:
        print(r)      
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글