[BOJ 1260]DFS와 BFS(파이썬)

문제링크

DFS와 BFS

풀이 전 계획 및 생각

DFS는 스택 BFS는 큐를 이용해서 풀기로 결정했다.
각 그래프는 빠른 조회를 위해서 딕셔너리를 이용해서 저장했다.
DFS와 BFS가 처음에는 이해가 어려웠는데 아래의 절차대로 생각을 하면서 문제를 푸니까 금방 풀렸다.

1. 방문할 노드를 큐/스택에서 꺼낸다.
2. visited에 방금 큐/스택에서 꺼낸 노드의 정보를 저장한다.
3. 지금 꺼낸 노드에서 갈 수 있는 노드들 중에서 visited에 없는 노드들만 큐/스택에 넣어준다.
4. 큐/스택이 비거나 주어진 조건을 만족할 때까지 1-3을 반복한다.

풀이

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited
 
def bfs(graph, start_node):
    visited = list()
    need_visit = list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

n,m,v = map(int,input().split())
G = dict()
for i in range(n):
    G[i+1] = []
for _ in range(m):
    n1, v1 = map(int,input().split())
    G[v1].append(n1)
    G[n1].append(v1)
for i in range(n):
    G[i+1].sort(reverse = True)
    
print(" ".join(map(str,dfs(G,v))))
for i in range(n):
    G[i+1].sort()
print(" ".join(map(str,bfs(G,v))))

풀이하면서 막혔던 점과 고민했던 점

기본적인 DFS와 BFS 문제였기때문에, 막히거나 고민했던 점은 없었다.

풀이 후 알게된 개념과 소감

마냥 어렵게만 느꼈던 BFS, DFS도 절차적으로 잘 정리하고서 접근하니 풀만하다는 걸 배웠다.