루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
과정
입력 받은 알파벳들을 정렬해준다.
dfs 함수를 활용해 탐색한다. 처음부터 끝까지 재귀하면 암호가 조건을 만족하지만 오름차순이 아닌 것들도 포함이 되기 때문에 이미 본 것은 포함하지 않게 인덱스(idx)를 인자로 받아서 재귀할 때 마다 1씩 늘려준다.
주어진 암호의 길이와 현재 암호의 길이가 같아지면 자음과 모음의 갯수를 세어서 조건을 만족할 경우 출력한 다음 함수를 종료한다.
예제 입력
7
1 6
6 3
3 5
4 1
2 4
4 7
예제 출력
4
6
1
3
1
4
풀이 (DFS - Python3)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n+1)
def dfs(v):
for i in graph[v]:
if not visited[i]:
visited[i] = v
dfs(i)
dfs(1)
for i in range(2, n+1):
print(visited[i])
파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 되는데 sys.setrecursionlimit(10**8) 를 통해 최대 재귀 깊이를 1,000,000 정도로 크게 설정하여 런타임 에러 없이 실행 시킬 수 있다.
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n+1)
노드의 개수 n 을 입력받는다.
정점 두개를 입력받고 각각 a위치에 b, b 위치에 a를 넣은 그래프를 만들어준다.
방문을 체크하기 위한 visited를 만들어준다.
def dfs(v):
for i in graph[v]:
if not visited[i]:
visited[i] = v
dfs(i)
dfs(1)
dfs 함수를 만들어준다.
노드를 입력받고 graph에서 그 노드와 연결된 노드를 가져온다.
만약 방문하지 않았다면 방문에 해당 노드 값을 넣어준다.
재귀하며 계속 탐색한다.
for i in range(2, n+1):
print(visited[i])
visited의 1번째 위치부터 출력해준다.
풀이2 (BFS - PyPy3)
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False]*(n+1)
parents = [0]*(n+1)
def bfs(start):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
for i in graph[v]:
if visited[i] == False:
parents[i] = v
queue.append(i)
visited[i] = True
bfs(1)
for i in range(2, n+1):
print(parents[i])
