[BOJ] 1260 DFS와 BFS

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

문제 요약

• n개의 정점과 m개의 간선의 개수가 주어진다.
• 시작 정점이 주어질 때 해당 그래프를 DFS, BFS로 탐색한 결과를 출력한다.

접근

• 무방향 그래프이므로 두 정점을 딕셔너리에서 이중으로 표현한다.

    ex)
	for i in range(1,m+1):
    	    u,v=map(int,sys.stdin.readline().rstrip().split())
    	    graph[u].append(v)
    	    graph[v].append(u)

• 중복으로 탐색하는 것을 방지하기 위해 이미 방문한 정점은 visited에 저장한다.
• DFS는 재귀를 사용하고 BFS는 큐를 사용한다.
  • DFS
    • dfs를 통해 방문한 정점인 경우 출력한다.
    • 정점과 연결된 다른 정점이 방문하지 않은 상태인 경우 해당 정점을 dfs로 탐색한다.
  • BFS
    • 시작 정점을 큐에 넣고 bfs 탐색을 시작한다.
    • 큐의 크기가 0이 될때까지 반복하면서 큐를 하나씩 꺼내 출력한다.
    • 인접한 정점이 방문하지 않은 상태인 경우 큐에 추가한다.
      

코드

import sys
from collections import deque

def dfs(s):
    if visited[s]:
        print(s,end=' ')
    for node in graph[s]:
        if not visited[node]:
            visited[node]=True
            dfs(node)

def bfs():
    print()
    visited=[False]*(n+1)
    que=deque([s])
    visited[s]=True
    while len(que)>0:
        node=que.popleft()
        print(node, end=' ')
        for i in graph[node]:
            if not visited[i]:
                visited[i]=True
                que.append(i)

n,m,s=map(int,sys.stdin.readline().rstrip().split())
graph=dict()
for i in range(1,n+1):
    graph[i]=[]

for i in range(1,m+1):
    u,v=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1,n+1): # 인접 정점 오름차순 정렬
    graph[i].sort()

visited=[False]*(n+1) # dfs에서 사용하는 visited 초기화
visited[s]=True

dfs(s)
bfs()