[백준] 24479번 깊이 우선 탐색1 (with python)

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

1. 내가 작성한 코드

 

dfs, bfs 넘나리 어렵다 ㅠ_ㅠ

 

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

n, m, r = map(int,input().split())
visit_dfs = [0] * (n+1)
graphs = [[]for _ in range(n+1)]
cnt = 1

for i in range(m):
  a,b = map(int, input().split())
  graphs[a].append(b)
  graphs[b].append(a)

for graph in graphs:
  graph.sort()

def dfs(graph,v,visit_dfs):
  global cnt
  visit_dfs[v] = cnt
  for i in graphs[v]:
    if visit_dfs[i] == 0:
      cnt+=1
      dfs(graph,i,visit_dfs)
    
dfs(graph, r, visit_dfs)

for i in range(n+1):
  if i!=0:
    print(visit_dfs[i])

 

인접행렬로 풀었더니 자꾸 메모리 초과가 떠서 구글링해서 풀었음 ㅠㅠ

 

2. 분석

1. PYTHON은 재귀 허용 깊이가 얕기 때문에 수동으로 늘려줘야해서 sys.setrecursionlimit(10**9) 를 적어야 한다.

=> DFS 문제를 풀 때 꼭 적기

 

2. 인접행렬(메모리↑, 속도↑) / 인접리스트(메모리↓,속도↓)

graphs = [[]for i in range(n+1)]

for i in range(m):
  a,b = map(int, input().split())
  graphs[a].append(b)
  graphs[b].append(a)

 

3. 함수 밖에 있는 변수를 사용하기 위해서는 global 을 명시해줘야함