백준 (BOJ) - 1260 DFS와 BFS [Python]

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

1260번: DFS와 BFS

 

오늘부터 BFS랑 DFS만 뒤지게 풀어볼 예정이라 본격적으로 들어가기 전 개념정리 느낌으로 가장 기본 문제를 풀이 해보았다.

우선 DFS는 깊이 우선 탐색이고 stack을 사용하는 알고리즘이며, BFS는 너비 우선 탐색이고 queue (보통 O(n)의 시간 복잡도를 갖는  deque)를 사용한다. 

 

우선 input으로 정점 개수, 간선 개수, 시작 노드를 받아주고 

graph라는 인접영행렬을 만들어준다.

그 후에 노드 정보를 모두 받아주는데 주의할 점은 graph[1][2]가 True면 graph[2][1]도 True 이런식으로 인접리스트를 생성해준다.

 

BFS는 인접 노드 중에 방문하지 않은 노드를 전부 큐에 삽입하고 방문처리 해주는 방식으로 코드를 짜면 된다. 

우선 시작 노드를 큐에 넣고 방문 처리 해줍니다. 

큐 안에 데이터가 없을 때까지 큐 맨 밑에 있는 값을 꺼내고 print해준다. 

1부터 N까지 만약 해당 값을 방문하지 않았고, V와 연결이 되어있는 노드라면 큐에 넣어주고 방문 처리 해준다.

 

DFS는 인접 노드 중에 최소값을 스택에 넣고 방문처리 해주는 방식으로 코드를 짠다.

우선 시작 노드인 V를 방문처리 해주고 print 해줍니다. 

그 후 현재 노드와 연결된 다른 노드를 재귀적으로 방문 해주는데, 1부터 N까지 만약 i번째 노드가 아직 방문하지 않았고, V와 연결 되어있는 노드라면 DFS(i)로 방문 처리 해주고 Print 해줍니다. 

from collections import deque
import sys

N, M, V = map(int, sys.stdin.readline().split())
# 정점 개수, 간선 개수, 시작 노드
graph = [[False] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (N + 1)  # dfs 방문기록
visited2 = [False] * (N + 1)  # bfs 방문기록


def bfs(V):
    queue = deque([V])
    visited2[V] = True  # 해당 V값을 방문 처리
    while queue:  # queue가 다 비면 종료
        V = queue.popleft()  # queue 맨 밑에 있는 값을 꺼낸 뒤에 출력
        print(V, end=" ")
        for i in range(1, N + 1): #1부터 N까지 돈다
            if not visited2[i] and graph[V][i]:  # 만약 해당 i값을 방문 하지 않았고 V와 연결이 되어 있다면
                queue.append(i)
                visited2[i] = True


def dfs(V):
    visited1[V] = True  # 첫번째 노드 방문
    print(V, end=" ")
    for i in range(1, N + 1): #1부터 N까지 돈다
        if not visited1[i] and graph[V][i]:  # 만약 해당 i값을 방문 하지 않았고 V와 연결이 되어 있다면
            dfs(i)


dfs(V)
print()
bfs(V)

 

다음 번엔 살짝 더 어려운 BFS와 DFS 문제를 들고 돌아오겠습니다.