[BOJ/Python] 1260 : DFS와 BFS

👉 문제 링크

오랜만에 푸는 문제여서 제일 쉬운 문제로 풀이를 공식처럼 외우던 탐색으로 시작했다.
너무 오랜만이라 그런지,,,,, 하나도 기억이 나지 않았다. 그래서 기본 구조부터 잡고 시작해보았다.

👉 알고리즘

dfs
1) 시작 노드를 방문 처리한다.
2) 현재 노드와 연결된 노드 중 방문하지 않은 노드가 있다면 방문 처리한다.
3) 방문하지 않은 인접 노드가 없다면 그 다음 노드에서 같은 과정을 반복한다.

def dfs(v):
	#v는 시작 정점
	visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(i)

bfs
1) 시작 노드를 큐에 삽입하고 방문 처리한다.
2) 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드가 있다면 모두 큐에 삽입하고 방문 처리한다.

def bfs(v):
	visited[v] = True
    
    que = deque()
    que.append(v)
    
    while que:
    	x = que.popleft()
        print(x, end=' ')
        
        for i in graph[x]:
        	if not visited[i]:
            	visited[i] = True
                que.append(i)

👉 풀이

문제의 조건에서 '방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.' 을 안봐서 한참을 생각했다.
이 조건 때문에 정렬이 필요했던 것!

for i in range(len(graph)):
	graph[i].sort()

👉 전체 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

#n: 정점 개수, m: 간선 개수, v: 시작 정점
n,m,v = map(int,input().split()) 

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i].sort()

#dfs
def dfs(v):
    visited[v] = True
    print(v, end= ' ')

    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(i)

#bfs
def bfs(v):
    visited[v] = True

    que = deque()
    que.append(v)

    while que:
        x = que.popleft()
        print(x, end=' ') 

        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                que.append(i)

visited = [False] * (n+1)
dfs(v)
print()
visited = [False] * (n+1)
bfs(v)