EDOC 2023-W 5회차 과제 (트리 알아보기 / 트라이)

09-1. 트리 알아보기

 

067. 트리의 부모 찾기 (백준 11725번)

 

https://www.acmicpc.net/problem/11725

 

from sys import stdin
import sys
sys.setrecursionlimit(10 ** 6)

n = int(stdin.readline())
g = [[] for _ in range(n+1)]
parent = [0] * (n+1)

def dfs(pre, cur):
    for nxt in g[cur]:
        if nxt != pre:
            parent[nxt] = cur
            dfs(cur, nxt)

for _ in range(n-1):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

dfs(0, 1)

for i in range(2, n+1):
    print(parent[i])

트리 정보를 저장한 후 한번 쭉 탐색하면서 부모 노드 정보를 기록해두면 되는 문제였다. 부모-자식 관계로 입력이 주어지면 g[a].append(b)만 하면 되지만, 이 문제에서는 그래프 연결 관계만 나와있기 때문에 마치 무방향 그래프처럼 g[a].append(b), g[b].append(a) 둘 다 해줘야 한다. 그리고 탐색할 때는 이미 탐색한, 즉 바로 이전 값인지 아닌지를 체크하기 위해서 pre값을 이용했다. (교재는 pre값 없이 visited 배열을 쓴 것 같았다.) 이 문제의 경우 깊이 탐색 (전위 순회, 중위 순회, 후위 순회)을 하든 너비 우선 탐색(레벨 순회)을 하든 상관없는 듯해서 나는 더 구현이 간단한 재귀를 사용하는 깊이 우선 탐색을 이용했다. (정답)

 

---

 

068. 트리 (백준 1068번)

 

 

https://www.acmicpc.net/problem/1068

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
delete = int(stdin.readline())
tree = [[] for _ in range(n)]
root = 0

for i in range(n):
    if data[i] == -1:
        root = i
    else:
        tree[data[i]].append(i)

def leaf(a):
    cnt = 0
    if len(tree[a]) == 0:
        return 1
    for nxt in tree[a]:
        cnt += leaf(nxt)
    return cnt

print(leaf(root) - leaf(delete))

처음에는 루트 노드에서 리프 노드 개수를 구한 것에서 삭제할 노드에서 리프 노드를 구한 것을 빼면 된다고 생각해서 이렇게 코드를 짰다. 그런데 78% 정도에서 틀려서 질문 게시판을 찾아보니 루트노드가 리프노드가 될 수 있다는 것을 간과한 것이었다. (오답)

# 반례
2
1 -1
0

정답 : 1

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
delete = int(stdin.readline())
tree = [[] for _ in range(n)]
root = 0

for i in range(n):
    if data[i] == -1:
        root = i
    else:
        tree[data[i]].append(i)

def leaf(a):
    cnt = 0
    if len(tree[a]) == 0:
        return 1
    for nxt in tree[a]:
        cnt += leaf(nxt)
    return cnt

if leaf(root) == leaf(delete):
    if delete == root:
        print(0)
    else:
        print(1)
else:
    print(leaf(root) - leaf(delete))

그래서 수정한 결과이다. 그래도 똑같이 78%에서 틀렸다. (오답)

# 반례
4
3 2 -1 2
0

정답 : 2

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
delete = int(stdin.readline())
tree = [[] for _ in range(n)]
root = 0

def leaf(a):
    cnt = 0
    if len(tree[a]) == 0:
        return 1
    for nxt in tree[a]:
        cnt += leaf(nxt)
    return cnt

for i in range(n):
    if data[i] == -1:
        root = i
    else:
        if delete != i:
            tree[data[i]].append(i)

if root == delete:
    print(0)
else:
    print(leaf(root))

지금까지는 계속 리프 노드에서 리프 노드를 빼는 방식으로 풀었는데, 애초에 이 방법이 틀린 것 같다는 생각이 들어 실제로 주어진 노드를 삭제하도록 구현을 하고 리프 노드를 구하는 방법으로 수정하였다. (정답)

 

---

 

09-2. 트라이

 

069. 문자열 집합 (백준 14425번)

 

https://www.acmicpc.net/problem/14425

 

from sys import stdin

n, m = map(int, stdin.readline().split())
s = []
cnt = 0

for _ in range(n):
    s.append(stdin.readline().strip())

for _ in range(m):
    string = stdin.readline().strip()
    for x in s:
        if x == string:
            cnt += 1

print(cnt)

그냥 생각이 떠오른 대로 푸니까 시간 초과가 났다. (오답)

 

from sys import stdin

n, m = map(int, stdin.readline().split())
s = []
cnt = 0

for _ in range(n):
    s.append(stdin.readline().strip())

s = set(s)

for _ in range(m):
    string = stdin.readline().strip()
    if string in s:
        cnt += 1

print(cnt)

set을 사용하여 푸니까 시간 초과가 해결되었다. (정답) 내일 꼭 트라이로 풀어야지...