[백준] 파이썬 - 1260 : DFS와 BFS

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

1260번: DFS와 BFS

실버 2. 백준 1260번 : DFS와 BFS
파이썬 풀이

 

 

코드

import sys
from collections import deque
input = sys.stdin.readline

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

dfs_list = []
bfs_list = []

for _ in range(m): # 그래프 생성
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)
    
for i in range(len(graph)) : # 그래프 내부 정렬
    graph[i] = sorted(graph[i])

def bfs(v) :
    visited = [False]*(n+1)

    queue = deque()

    queue.append(v)
    bfs_list.append(v)

    while queue:
        l = queue.popleft()
        visited[l] = True

        for k in graph[l] :

            if visited[k] == False:
                visited[k] = True
                queue.append(k)
                bfs_list.append(k)
            
visited_dfs = [False] * (n+1)

def dfs(v) :
    visited_dfs[v] = True 
    dfs_list.append(v)

    for i in graph[v] :
        if not visited_dfs[i] : 
            dfs(i)

dfs(v)
print(*dfs_list)

bfs(v)
print(*bfs_list)

 

간단하게 dfs와 bfs 사용하면 돼서 풀이 생략!

이제는 dfs와 bfs 어느정도는 풀 수 있는 거 같아서 다행이다 물론 꼬아서 나오면 아직도 힘들지만...

 

처음에 헷갈렸던 부분은, 예전에 dfs 풀때 회귀를 너무 많이 하게 되면 메모리 초과.. 어쩌고 된다고 해서 처음에 풀 때부터 

" sys.setrecursionlimit(10**7) "

이거 걸어두고 시작했었는데, limit이 너무 컸던 거 같다..^^ 이것때문에 오히려 메모리 초과가 났음. 삭제하고 나니까 되더라.... 

언젠가는 잘 하겠거니!!!!!! 

 

 

 

https://github.com/eunnnju/24repo

GitHub - eunnnju/24repo

 

깃허브도 놀러오세요~~ ^^