https://www.acmicpc.net/problem/24479
24479번: 알고리즘 수업 - 깊이 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
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 을 명시해줘야함
'🔅코딩테스트 공부🔅 > ❗백준' 카테고리의 다른 글
[백준] 2667번 단지번호붙이기(with python) (0) | 2023.02.08 |
---|---|
[백준] 2606번 바이러스(with python) (0) | 2023.02.08 |
[백준] 1260번 DFS와 BFS (with python) (0) | 2023.02.07 |
[백준] 15469번 N과 M (1)(with python) (0) | 2023.02.04 |
[백준] 2108번 통계학(with python) (0) | 2023.02.02 |
댓글