[백준] 14725번 개미굴 _ Python

[초기 접근 방법]

1) 개미굴 입구를 중심으로, 자식 노드들을 top [] 에 저장한다.

2) 자식노드들의 각 행에 중복되지 않는 노드들을 result[] 에 저장하도록 한다.

 

 

 

[생각]

각 행에 중복되지 않는 노드들을 result[]에 저장하도록 구현했는데,

부모 노드가 다를 때에는 각각 저장해주어야 한다.

아래와 같은 test case 를 적어보았다.

 

Input	Output	Answer
2 3 APPLE APPLE ORANGE 3 APPLE BANANA ORANGE	APPLE --APPLE ----ORANGE --BANANA	APPLE --APPLE ----ORANGE --BANANA ----ORANGE

 

 

 

올바른 접근 풀이는 다음과 같다.

 

 

1. 동굴 깊이 간선 정보를 정렬을 한다.

→ 사전 순서가 앞서는 정보가 먼저 나오기 때문

 

2. 첫번째 깊이 간선은 result 에 깊이에 따라 바로 추가한다.

 

3. i(>=2)번째 간선부터는 cave[i][j] 와 cave[i-1][j] 값을 비교하며, 새로운 값이 등장할 시 result에 추가한다.

- 한 가지 유의할 점이 cave[i]의 길이가 cave[i-1]보다 길어질 경우 "len(cave[i-1]) <= j" 길이 체크를 반드시 해주어야 한다.

그렇지 않을 경우 IndexError: list index out of range 가 발생한다.

 

 

 

 

[코드]

- 틀린 코드

import sys
input = sys.stdin.readline

N = int(input().strip())

cave = []
depth = 0
for _ in range(N):
    lst = list(map(str, input().strip().split()))
    depth = max(depth, int(lst[0]))
    cave.append(lst[1:]) # cave 정렬을 위해서 삭제해야 함

cave.sort() # 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나와야 한다.

top = [] # 루트 자식노드 리스트
result = [] # 결과

for i in range(N):# 중복 제거
    if cave[i][0] not in top: # top 아니라면 추가
        top.append(cave[i][0])
        result.append(cave[i][0])
        idx = len(result) # 첫번째 노드 인덱스 관리

    for j in range(1, len(cave[i])):
        if ("--" * j) + cave[i][j] not in result[idx:]: # 첫번째 노드를 추가하고, 이후 자식 노드들 사이에서의 중복 노드 관리
            result.append(("--" * j) + cave[i][j])

for r in result:
    print(r)

 

 

 

- 정답 코드

# 시간 복잡도 : O(Nlog(N) + N * K)
    # Nlog(N) : 정렬 시간 복잡도
    # N*K : 현재 동굴 정보와 이전 동굴 정보가 일치하는지 체크(K)하면서 N개의 동굴 탐색
# 공간 복잡도 : O(N)

# 참고 : https://velog.io/@kimdukbae/BOJ-14725-%EA%B0%9C%EB%AF%B8%EA%B5%B4-Python

import sys
input = sys.stdin.readline

N = int(input().strip())

cave = []
depth = 0
for _ in range(N):
    lst = list(map(str, input().strip().split()))
    depth = max(depth, int(lst[0]))
    cave.append(lst[1:]) # cave 정렬을 위해서 삭제해야 함

cave.sort()

result = [] # 결과
top = [] # 루트 자식노드 리스트

for i in range(N):
    # 초기 동굴 구성
    if i == 0:
        for j in range(len(cave[i])):
            result.append(("--" * j) + cave[i][j])

    else:
        idx = 0
        for j in range(len(cave[i])):
            # 이전 정보와 겹치지 않거나, 겹치다가 현재 동굴의 길이가 더 깊어 표현할 수가 없을 때
            if cave[i-1][j] != cave[i][j] or len(cave[i-1]) <= j: # j → len(cave[i]) X
                break
            else:
                idx = j + 1

        # 겹치지 않는 시점부터, "-- + 하위 노드"를 추가한다.
        for j in range(idx, len(cave[i])):
            result.append("--" * j + cave[i][j])

for r in result:
    print(r)