백준 1260 DFS와 BFS Python 3

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

1260번: DFS와 BFS

 

최종 코드

• GitHub -> https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

import sys
from collections import deque
global dfs_result, bfs_result
dfs_result, bfs_result = "", ""
def DFS(now, visit, edge):
    global dfs_result
    dfs_result += (str(now) + " ")
    visit[now] = 1
    next = sorted(edge[now][:])
    for n in next:
        if visit[n]: continue
        DFS(n, visit, edge)

def BFS(V, edge, visit):
    global bfs_result
    q = deque([V])
    while q:
        now = q.popleft()
        if visit[now]: continue
        visit[now] = 1
        bfs_result += (str(now) + " ")
        next = sorted(edge[now][:])
        for n in next:
            if visit[n]: continue
            q.append(n)

input = sys.stdin.readline
N, M, V = map(int, input().split())
edge = [[] for _ in range(N+1)]
for _ in range(M):
    v1, v2 = map(int, input().split())
    edge[v1].append(v2)
    edge[v2].append(v1)
visit = [0]*(N+1)
DFS(V, visit, edge)
visit = [0]*(N+1)
BFS(V, edge, visit)
print(dfs_result)
print(bfs_result)

---

풀이 과정

풀이 시간 32분

기본적인 DFS, BFS 탐색이다

그래프가 Edge 연결 상태로 주어지는 인접 리스트 방식이고, 한 노드에 연결된 간선이 여러 개인 경우 정점의 번호가 작은 순서대로 탐색하는 것이 핵심이다.

import sys
from collections import deque

global dfs_result, bfs_result
dfs_result, bfs_result = "", ""

def DFS(now, visit, edge):
    global dfs_result
    dfs_result += (str(now) + " ")
    visit[now] = 1
    
    #번호가 작은 순서대로 탐색하기 위해 연결된 노드 정보를 정렬한다
    next = sorted(edge[now][:])
    for n in next:
        if visit[n]: continue
        DFS(n, visit, edge)

def BFS(V, edge, visit):
    global bfs_result
    q = deque([V])
    while q:
        now = q.popleft()
        if visit[now]: continue
        visit[now] = 1
        bfs_result += (str(now) + " ")
        
        #번호가 작은 순서대로 탐색하기 위해 연결된 노드 정보를 정렬한다
        next = sorted(edge[now][:])
        for n in next:
            if visit[n]: continue
            q.append(n)

input = sys.stdin.readline
N, M, V = map(int, input().split())

#인접 리스트 만들기
edge = [[] for _ in range(N+1)]
for _ in range(M):
    v1, v2 = map(int, input().split())
    edge[v1].append(v2)
    edge[v2].append(v1)
    
visit = [0]*(N+1)
DFS(V, visit, edge)

visit = [0]*(N+1)
BFS(V, edge, visit)

print(dfs_result)
print(bfs_result)

#시간복잡도 = O((N+M) * M log M), 공간복잡도 = O(M)