[백준] 1260번: DFS와 BFS

😎BACKJOON>1260번: DFS와 BFS

---

📘 문제풀이

from collections import deque

n, m, startV = map(int, input().split())

graph = [[0]*(n+1) for j in range(n+1)]

for _ in range(m):
    x, y  = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False]*(n+1)

#DFS
def dfs(v):
    
    visited[v] = True
    print(v, end= ' ')
    
    for u in range(1, n+1):
        if graph[v][u] == 1 and not visited[u]:
            dfs(u)  
    
#BFS
def bfs(s):
    visited = [False]*(n+1)
    
    queue = deque([s])
    visited[s] = True
    
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for u in range(1, n+1):
            if not visited[u] and graph[v][u] == 1:
                queue.append(u)
                visited[u] = True
                
dfs(startV)
print()
bfs(startV)

👍 더 빠른 문제풀이

from collections import deque
import sys

n, m, v = map(int, sys.stdin.readline().split())

graph = [[0]*(n+1) for j in range(n+1)]
visited = [0]*(n+1)

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

    for u in range(1, n+1):
        if graph[v][u] == 1 and not visited[u]:
            dfs(u)
  
def bfs(s):
    visited = [0 for i in range(n+1)]
    queue = deque([s])
    visited[s] = 1
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for u in range(1, n+1):
            if graph[v][u] == 1 and not visited[u]:
                visited[u] = 1
                queue.append(u)
                
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1

dfs(v)
print()
bfs(v)

sys를 사용하여 입력을 받으면 시간이 더 줄어든다.