❓문제
https://www.acmicpc.net/problem/24479
❗문제 정리
사용한 파라미터:
n(int) : 0번노드를 포함한 정점의 개수
m(int) : 간선의 수
r(int) : 시작노드의 번호
graph(int, list) : dfs를 사용하기 위한 graph
visited(int, list) : 방문처리를 위한 리스트로 초기 0으로 채워져 있음
count(int) : 순서를 출력하기 위한 변수. 노드 1번부터 시작하므로 1로 초기화해서 시작.
top_node(int) : 최상단 노드를 입력받기 위한 변수
connected_node(int) : 최상단 노드와 연결되어있는 노드를 입력받기 위한 변수
사용한 기능:
📑코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m, r=map(int, input().split())
graph=[[] for i in range(n+1)]
visited=[0]*(n+1)
count=1
for i in range(m):
top_node, connected_node=map(int, input().split())
graph[top_node].append(connected_node)
graph[connected_node].append(top_node)
def dfs(graph,start_node, visited):
#1. 현재 방문한 노드는 방문처리
global count
visited[start_node]=count
graph[start_node].sort()
#2. 최상단노드의 인접노드에 방문하지 않았다면0이라면,그곳을 최상단노드로 방문처리하고 인접노드 방문하기
for i in graph[start_node]:
if visited[i]==0:
count+=1
dfs(graph,i, visited)
dfs(graph,r, visited)
for i in range(1, len(visited)):
print(visited[i])
📝코드 설명
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m, r=map(int, input().split())
graph=[[] for i in range(n+1)]
visited=[0]*(n+1)
count=1
재귀가능 범위를 늘림
파라미터 입력받기
그래프를 만들기 위한 2차원 공간의 간선의 수 크기의 빈 배열 생성
방문처리를 위한 0으로 채워진 간선의 수 크기의 visited 리스트 생성
: 0으로 채우는 이유는 시작 정점에서 방문할 수 없는 경우 0을 출력하라는 문제지시에 따름.
순서를 출력하기 위한 변수 count를 1로 초기화함.
for i in range(m):
top_node, connected_node=map(int, input().split())
graph[top_node].append(connected_node)
graph[connected_node].append(top_node)
def dfs(graph,start_node, visited):
global count
visited[start_node]=count
graph[start_node].sort()
for i in graph[start_node]:
if visited[i]==0:
count+=1
dfs(graph,i, visited)
start_node가 1이므로, 인덱스 1부터 시작.
global로 count를 선언하여 public으로 변수값 공유.
[문제예시1]
[문제예시2]
🎖제출 결과
💡insight
[반례]
[input]
6 4 1
2 3
1 4
1 5
4 6
[output]
1
0
0
2
4
3