3. 이제는 친숙해진 DFS, BFS (백준 1260 파이썬)

처음 배웠을 때는 충격과 공포였는데, 이제는 오히려 안심이 되는(?) 친근해진 DFS, BFS다.

생각보다 개념은 단순하게, 트리모양을 보면 이해가 빨리 되고, 실제 문제를 풀 때 내가 가장 쉽게 이해한 방법은:

• DFS는 stack, 그리고 재귀는 결국 stack이므로 재귀로 풀 수 있음
• BFS는 queue, 그래서 더 쉽긴한데 pop(0)이 좀 효율성이 안좋다

이외에 좀 주의해야 하는 부분은 입력 값을 어떻게 저장하는가 부분이다. 사실 그래프 유형과 DFS BFS 유형도 비슷한 것 같고,, 재귀로 푸는 문제들도 서로서로 비슷한 것 같고.. 약간 딱 나눠서 할 수 있나 싶은데 (백준에서도 브루트포스 재귀로 분리되어 있는 문제가 DP로 풀기도 하고..) 여튼 그래프 형식은 노드, 간선, 시작점 입력에 익숙해지면 그래도 좀 낫다.

 

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

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

---

각각 함수를 만들어서 풀었다. DFS는 재귀를 쓰고 싶어서 함수 필수,,

사실 전역 변수 접근을 이렇게 하면 안좋다는 것을 알지만... 난 초심자니까(?)

import sys
sys.stdin = open('1260.txt')

N, M, V = map(int, sys.stdin.readline().split())

G = [[0] * (N+1) for _ in range(N+1)]
for i in range(M):
    A, B = map(int, sys.stdin.readline().split())
    # 그래프 쌍방으로 넣어줘야 함
    G[A][B] = 1
    G[B][A] = 1

visited = [0]*(N+1)
answer1 = []
def DFS(V):
    if visited[V] == 0:
        answer1.append(V)
        visited[V] = 1

        # 어떤 값을 돌며 어떤 값으로 넘어갈지 주의
        for i in range(1, N+1):
            if G[V][i] == 1 and visited[i] == 0:
                DFS(i)


answer2 = []
def BFS(V):
    my_queue = [V]
    visited2 = [0]*(N+1)
    while my_queue:
        temp = my_queue.pop(0)
        if visited2[temp] == 0:
            answer2.append(temp)
            visited2[temp] = 1
            for i in range(1, N+1):
                if G[temp][i] == 1 and visited2[i] == 0:
                    my_queue.append(i)


DFS(V)
BFS(V)
print(' '.join(map(str, answer1)))
print(' '.join(map(str, answer2)))

이전에는 이중 배열에서도 노드별로 이어진 애들 저장을 하는 방식으로 (ex. 1-2가 연결되어 있으면 [[0], [2], [1]] 이런 느낌), 이 방법으로 했을 때 순서가 내가 원하는 방향으로 안가서 (이건 아직도 왜인지 모르겠음..) 안전하게 모든 값에 대해서 표를 만들고 이어져 있으면 1을 넣는 식으로 했다. (ex. [[0, 0, 0], [0, 0, 1], [0, 1, 0]])

 

사실 이 문제 한참 배울때도 도전했던 문제인데 (무려 1년전 실화인가?) 대체 왜 ValueError를 얻고 장렬하게 포기했는지 모르겠다ㅋㅋㅋ 어쨌든 풀어서 너무 행복함