알고리즘 수업 - 깊이 우선 탐색2

yongju·2022년 11월 21일

BAEKJOON

목록 보기

2/40

❓문제
https://www.acmicpc.net/problem/24480

❗문제 정리
사용한 파라미터:
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) : 최상단 노드와 연결되어있는 노드를 입력받기 위한 변수

사용한 기능:

재귀가능 범위 확대 sys.setrecursionlimit(number)
문자열입력받기 sys.stdin.readline()
: 반복문으로 여러줄 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않음.
DFS
💡이전 문제는 오름차순으로 방문, 이번 문제는 내림차순(reverse=True)으로 방문함

📑코드

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(reverse=True)

  #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)

DFS를 구현하기 위한 그래프 제작
0번노드부터 끝 번호노드를 인덱스로하여 이와 연결된 노드들을 해당 인덱스에 리스트로 넣는다. 0번 노드는 비워두도록한다.
e.g) 1번노드와 연결되었다면 인덱스 1의 자리에 1번노드와 연결된 노드번호를 하나씩 넣도록한다.
[graph 예시]

def dfs(graph,start_node, visited):

    global count
    visited[start_node]=count
    graph[start_node].sort(reverse=True)

    for i in graph[start_node]:
        if visited[i]==0:
            count+=1
            dfs(graph,i, visited)

start_node가 1이므로, 인덱스 1부터 시작.
global로 count를 선언하여 public으로 변수값 공유.
[문제예시1]