[ 2023-07-19 🍄 TIL ]

백준 24779번 파이썬

---

문제

---

코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**6) 
## RecursionError가 발생하지 않기 위해 재귀의 깊이를 설정
## Pypy일 때는 10**5 
## python 제출일때는 10**6 으로 설정 
n, m, v = map(int,input().split())

graph = [[] for _ in range(n+1)]
# [[0] * (n+1) for _ in range(n+1)]
# 위와 같이 설정한 경우애 메모리에러가 발생한다. 
# 또한 오름차순으로 노드 탐색하기 위해서 노드의 값을 넣어주는 빈배열로 설정

visited = [0 for _ in range(n+1)]
count = 1
for _ in range(m):
  n1, n2 = map(int,input().split())
  graph[n1].append(n2)
  graph[n2].append(n1)
  
for nodes in graph: # 오름차순으로 노드를 탐색하기 위한 정렬
    nodes.sort()
    
def dfs(s):
  global count
  visited[s] = count 
  # 노드에 방문기록으로 기록한다.
  # 인덱스 값이 노드를 나타냄
  for i in graph[s]:
    if (not visited[i]):
      count += 1
      dfs(i)

dfs(v)

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

python에서는 재귀를 사용하는 것이 비효율적입니다.
그렇기에

재귀를 사용하지 않고 DFS를 구현하는 방법을 chat-gpt에게 물어보았습니다.

def dfs(graph, start):
    stack = [start]
    visited = set()

    while stack:
        current_node = stack.pop()

        if current_node not in visited:
            print(current_node)
            visited.add(current_node)

            # 현재 노드의 인접 노드들을 스택에 추가
            for neighbor in graph[current_node]:
                if neighbor not in visited:
                    stack.append(neighbor)

# 그래프 예시 (인접 리스트 방식)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3]
}

dfs(graph, 1)

그래프에 공부에 대한 필요성을 느끼고 DFS부터 차근차근 공부해보기로 하였습니다.
한동안은 DFS를 공부하고 일정 수준의 문제를 혼자 풀 수 있으면 BFS로 넘어가 공부를 해 볼 예정입니다.