1068번 - 트리

트리가 주어질 때, 노드를 하나 고르고 해당 노드의 하위노드까지 싹 다 지웠을 때 리프 노드의 개수의 합을 구해내는 문제입니다.

N = int(input())
graph = [[0]*N for _ in range(N)]
lst = list(map(int,input().split()))
erase = int(input())
visited = [0]*N

먼저 기본적인 입력을 받습니다.
lst의 각 인덱스마다 연결된 노드가 표시됩니다. 예를 들어 0번 인덱스에 1이 있다면 노드 0과 노드 1은 연결되어 있다는 뜻입니다. -1은 부모가 없을 경우 인덱스의 들어있는데 해당 인덱스는 루트 노드라고 봐도 무방할 것 같습니다.

sum = 0
for values in lst:
    if values == -1:
        sum += 1
        continue
    else:
        graph[sum][values] = graph[values][sum] = 1
    sum += 1

그래프의 2차원배열로써 트리를 구현하겠습니다. 그래프[인덱스][벨류] = 그래프[벨류][인덱스] = 1로 표시하여 노드끼리 서로 연결되어 있음을 나타내주겠습니다.

for i in range(len(graph)):
    for j in range(len(graph[0])):
        if i == erase:
            graph[i][j] = 0
        if j == erase:
            graph[i][j] = 0

저희는 노드와의 연결을 끊기 위한 erase 라는 변수를 받았습니다. 이제 erase와 연결되어 있는 노드가 graph에 있다면 죄다 0으로 만들어 노드 사이의 연결을 끊어줍시다.

ans = 0
dfs(lst.index(-1))

이제 dfs를 루트노드부터 돌리기 시작하겠습니다.
0이 루트노드가 아닐 수 있어서 만약 0부터 돌리면 결과값이 틀리게 나올 수도 있습니다.

def dfs(N):
    global ans
    visited[N] = 1
    boolean = False

N이 들어오면 방문표기를 해주고

    for i in range(len(graph)):
        if graph[N][i] == 1 and not visited[i]:
            boolean = True
            dfs(i)

N과 연결된 접점이 있다면 그 노드에 가서 재귀를 활용해 또 탐색해줍시다.
여기서 제가 boolean값을 썼는데 이건 리프노드를 구분하기 위함입니다. 예를 들어서 다 방문했고 저기 위에 적혀있는 if식이 아예 발동되지 않으면 그건 탐색이 막 끝났다는 의미이므로 boolean은 False값을 유지하고 현재 탐색이 진행중인 값은 리프노드가 될 것입니다. 그러므로

    if boolean == False:
        ans += 1

리프노드가 된다면 ans의 카운트를 1 올려줍시다.

if lst.index(-1) == erase:
    print(0)
else:
    print(ans)

마지막으로 루프 노드를 지워버리면 리프노드는 존재하지 않으므로 0을 출력하고 (다지워지니까)
아니면 ans를 출력하면 정상적으로 답을 도출할 수 있습니다.

---

21937번 - 작업

이 문제는 문제 자체보다 메모리 초과와 시간 초과 등 각종 오류를 피하는게 어려웠습니다...
일단 문제는 작업 흐름이 있고, 리프 노드를 작업하기 위해선 그 전 작업 흐름의 노드를 작업해야 합니다.
노드가 주어질 때, 몇 개의 이전 노드를 작업해야 해당 노드를 작업할 수 있는지 묻는 문제입니다.

푸는 개념 자체는 어렵지 않습니다. 주어진 노드의 역순으로 그래프 순서를 만들어주고
(1->6 이라면 6->1로) 그렇게 완성된 역순그래프에서 주어진 노드의 하위노드 개수를 세주면 끝납니다.

---

처음에 풀었던 방식

N,M = map(int,input().split())
graph = [[0]*(N+1) for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    graph[b][a] = 1

N과 M을 입력받아주고 graph를 [0]이 N+1개만큼 들어있는 이차원 배열로 선언합니다.
그리고 graph[b][a]를 1로 선언함으로써 b->a인 역순그래프를 생성합니다.

work = int(input())
sum = 0
dfs(work)

주어진 노드를 받아주고 해당 노드의 하위노드 개수를 구하기 위해서 dfs를 돌립니다.

def dfs(N):
    global sum
    visited[N] = 1
    for i in range(len(graph)):
        if graph[N][i] == 1 and not visited[i]:
            sum += 1
            dfs(i)

방문표기를 해준 후 그래프 길이만큼 돌리고 만약 해당 노드와 연결된 게 있고 방문을 안했으면 sum값을 1 높여주고 하위노드로 다시 재귀를 돌립시다.

print(sum)

그리고 출력하면

답은 정상적으로 나오는데

메모리 제한이 걸립니다!
이걸 해결하기 위해 생각을 거듭해봤습니다.

---

메모리 제한 해결

여기서 메모리 제한이란 재귀의 크기에 중점을 잡기보다는 배열의 크기가 너무 커서 일어난 일 같습니다.

질문글을 올려보니 메모리 크기가 10GB가 넘을것 같다고 하시네요...
따라서 배열을 최대한 적게 활용하는 방향으로 코드를 짜봤습니다.

N,M = map(int,input().split())
graph = [[] for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    graph[b].append(a)

일단 이차원 리스트의 이차원 요소를 하나로 고정시켰습니다.
[[0,0,0,0,0,0],[0,0,0,0,0,0,],....] 이었던 걸 [[],[]] 로 만들었습니다.
그리고선 이어진 걸 표현하기 위해 역순 그래프의 끝점 노드를 인덱스, 역순 그래프의 시작점 노드를 value값으로 잡아 해당 노드들이 이어졌다는 것을 표현하려고 했습니다.

work = int(input())
sum = 0
dfs(work)

그 외 과정은 비슷하며

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

이따 해보니 시간초과까지 나서 sysinput하고 recursionlimit 까지 설정해주었습니다.

def dfs(N):
    global sum
    visited[N] = 1
    for i in graph[N]:
        if not visited[i]:
            sum += 1
            dfs(i)

여기도 이전코드와 조금 다른데, 해당 노드가 들어오면 해당 인덱스에 접근해서 (둘이 이어진 노드니까) 만약 해당 인덱스에 아직 방문을 안한 상태라면 재귀를 돌려 방문해주는 형식으로 코드를 작성했습니다.

print(sum)

출력은 동일합니다.

제가 항상 BFS나 DFS쓸 때 노드들이 이어졌다는 걸 저런씩으로 표현하다 보니 발생한 문제같습니다.
앞으로 이차원 리스트를 사용할 때는 메모리 제한까지 고려해서 좀 더 변수들을 효율적으로 쓸 수 있도록 선언해야겠습니다.

---

---