백준 - 1260번 DFS와 BFS

---

---

출처:1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

---

DFS와 BFS 성공 분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

119226

41817

24050

33.325%

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

[설명]

 

이 문제는 기본적으로 DFS, BFS 가 어떤 원리로 동작하는지 물어보는 문제이다.

DFS, BFS는 사실 이 그림만 이해하면 전부 이해했다고 볼 수 있습니다.

 

그림 1 - DFS & BFS 설명

 

DFS는 자기 위치에서 먼저 연결돼있는 걸 확인하고, 그다음 먼저 연결돼있는 걸 확인하는 방식

BFS는 자기 위치를 기준으로 모든 연결부위를 확인하는 방식, 그다음 넘어가서 자기 위치에서 모든 연결부위를 넘어가는 걸 반복하면서 확인하는 방식입니다.

 

---

코드 :

 

def DFS(num):
    print(num, end=' ')  # 처음 방문한 그 지점을 출력
    visited[num] = 1  # 방문했을 때 그 방문리스트에 0으로 되어있을 텐데, 그것을 1로 바꾸어준다.
    for i in range(N+1):
        if visited[i] == 0 and connectList[num][i] == 1:
            DFS(i)

def BFS(num):
    result = [num]
    visited[num] = 0  # 아까 DFS함수를 돌면서 visited리스트의 인덱스값을 모두 1로 바꾸어 주었던 상태이므로 1인상태가 방문을 안한상태이니까 방문을 했을 경우 0으로 바꾸어준다.
    while result:
        num = result[0]
        print(num, end=' ')
        del result[0]
        for i in range(N+1):
            if visited[i] == 1 and connectList[num][i] == 1:
                # print(result)
                result.append(i)
                visited[i] = 0

import sys
N, M, V = map(int, sys.stdin.readline().split())
# N이 정점 개수, M이 간선 개수, V가 시작정점 이라고 생각하고 그래프를 그리는 것이라고 생각하고 코딩 시작.
# 간선 개수>
# 그래프를 컴퓨터가 이해하도록 설계하려면 matrix로 설계를 해야 컴퓨터가 이해를 합니다.
# matrix를 설계와 동시에 초기화까지 시켜줍니다.

connectList = [[0] * (N + 1) for _ in range(N + 1)]
# print(ablist)
# 내가 방문한 점을 또 방문하면 안되니까 visited라는 1차원 행렬을 만들어줍니다.
visited = [0 for _ in range(N+1)]
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    connectList[a][b] = 1
    connectList[b][a] = 1

DFS(V)
print()
BFS(V)

 

---

후기

 

DFS, BFS를 오랜만에 봐서 까먹었다가 개념을 다시 잡고 풀어 봅니다.

복습 과정에서 많은 그림 중 저 그림처럼 설명하는 게 이해가 가장 와 닿아서 설명해봅니다.