[ 2023-07-20 🎋 TIL ]

백준 11725, 24480번 파이썬

11725번

---

문제

---

코드

import sys

input = sys.stdin.readline

n = int(input())
graph = dict()
visited = [0 for _ in range(n+1)]

for _ in range(n-1):
  n1, n2 = map(int, input().split())
  if (n1 in graph):
    graph[n1].append(n2)
  else:
    graph[n1] = [n2]

  if (n2 in graph):
    graph[n2].append(n1)
  else:
    graph[n2] = [n1]
    
stack = [1]
print('graph :: ', graph)
while stack:
  p = stack.pop() # 부모 노드
  
  for i in graph[p]: # p의 자식 노드 탐색
    if not visited[i]: 
    # 아직 탐색 안한 노드 있으면 탐색할 노드로 추가
      visited[i] = p # 자식 노드에 부모를 저장
      stack.append(i)


for i in range(2, n+1): # 1은 제외한 노드의 부모 노드만 출력
  print(visited[i])

---

24480번

문제

---

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(1+n)]

for _ in range(m):
  n1,n2 = map(int, input().split())
  graph[n1].append(n2)
  graph[n2].append(n1)
  
for i in range(1, n+1):
  graph[i] = reversed(sorted(graph[i])) 
# 내림차순 탐색을 위해서 내림차순으로 정렬

turn = 1
def dfs(s):
  global turn 
  visited[s] = turn # 방문순서
  turn += 1 

  for i in graph[s]:
    if not visited[i]: # 방문했는지 확인
      dfs(i)
      
dfs(v)

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

DFS 개념 문제풀면서 이해중..
재귀로도 풀어보고.. 반복문만으로 풀어보고..
다음은 응용 문제를 풀어볼 예정