1260 DFS와 BFS

💡문제 분석 요약

• DFS, BFS 기본 문제이다.
• N개의 정점과 M개의 간선이 주어지고 V 노드에서 탐색을 시작한다.
• V를 시작으로 방문된 점을 순서대로 출력하면 된다.

💡알고리즘 설계

• 정점 탐색을 위한 그래프를 사용한다.
• DFS는 스택 or 재귀로 풀 수 있다.
• BFS는 큐를 이용하여 풀 수 있고, 큐는 웬만하면 deque를 선언하는 것이 좋다고 느낀다.

💡코드

from collections import deque

n, m, v = map(int, input().split()) # 정점, 간선, 탐색 시작할 정점의 번호
graph = [[False] * (n + 1) for _ in range(n + 1)] # 그래프 선언

# 주어진 정보로 정점간 연결하기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (n + 1)  # dfs 방문기록
visited2 = [False] * (n + 1)  # BFS 방문기록
############################################## 초기세팅 끝

def DFS(v):
    visited1[v] = True # 현재 노드는 방문한것
    print(v, end=' ') # 방문한 노드 출력
    for i in range(1, n+1):
        if visited1[i] == False and graph[v][i] == 1: # 아직 방문하지 않았고, 연결되어 있는 경우
            DFS(i) # 방문하지 않은 노드 계속 방문

def BFS(v):
    queue = deque([v])
    visited2[v] = True # 현재 노드는 방문한것

    while queue:
        v = queue.popleft()
        print(v, end=' ') # 방문한 노드 출력
        for i in range(1, n+1):
            if visited2[i] == 0 and graph[v][i] == 1:
                queue.append(i)
                visited2[i] = 1 # 방문처리
    return queue

DFS(v)
print()
BFS(v)

💡시간복잡도

• DFS, BFS 둘 다 모든 정점에 대해서 연결 노드를 검사하므로 O(N^2)이 될 것으로 보인다.

💡 틀린 이유

• 그래프 라는 자료구조 자체를 많이 안다뤄봐서 더 어려워보였다. 그래프를 공부해보고 정리해야겠다.
• DFS, BFS 문제 자체를 많이 안풀어봐서 접근법을 몰랐다. 많이 풀다보면 해결될 것이다.
• visited[i] 라고 해야하는데 visited 라고만 써서 값이 안나오는 문제도 있었는데, 파이참에서도 밑줄이 그어지지 않는 부분이기 때문에 디버깅 할 때 오래걸렸다. 마치 ==을 =이라고 쓴 느낌인데 이런 것들은 항상 조심해야한다.

💡 틀린 부분 수정 or 다른 풀이

• 노드를 관리함에 있어서 SET을 이용하는 풀이가 있었다. 이를 이용하여 풀어보고 정리해본다. 

💡 느낀점 or 기억할정보

• 그래프 공부하고 내용 정리하기
• BFS, DFS 접근법과 format 익히기