백준 알고리즘 | 1260 : DFS와 BFS (Python / 파이썬)

---

DFS와 BFS 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	104340	35681	20595	32.556%

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

1260번: DFS와 BFS

---

문제

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

​

입력

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

​

출력

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

​

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

---

 

백준 알고리즘 # 1260번 : DFS와 BFS

n, m, v = map(int, input().split())

matrix = [[0] * (n + 1) for i in range(n + 1)]
'''
[[0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]
'''

for i in range(m):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1
'''
   0  1  2  3  4
0[[0, 0, 0, 0, 0],
1 [0, 0, 1, 1, 1],
2 [0, 1, 0, 0, 1],
3 [0, 1, 0, 0, 1],
4 [0, 1, 1, 1, 0]]
'''

visit = [0] * (n + 1)
# [0, 0, 0, 0, 0]

def dfs(v):
    visit[v] = 1    # 방문한 점 1로 표시
    print(v, end = " ")
    for i in range(1, n + 1):
        if (visit[i] == 0) and (matrix[v][i] == 1):
            dfs(i)

def bfs(v):
    queue = [v]     # 들려야 할 정점 저장
    visit[v] = 0    # 방문한 점 0으로 표시
    while queue:
        v = queue.pop(0)
        print(v, end = " ")
        for i in range(1, n + 1):
            if (visit[i] == 1) and (matrix[v][i] == 1):
                queue.append(i)
                visit[i] = 0

dfs(v)
print()
bfs(v)

풀이

DFS(Depth First Search), 깊이 우선 탐색

BFS(Breadth First Search), 너비 우선 탐색

그래프 탐색 문제를 처음 풀어서 문제를 코드로 옮기는데 상당한 시간이 걸려서 구글링을 했어요..😂

정보처리기사 공부하면서 봤던 개념이라 DFS, BFS를 이해하는 것은 괜찮았는데

이 개념을 기계가 이해하게끔 코드로 변환하려면 2차원 배열을 이용해야 되더라구요!

[[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0]]

위와 같이 n, m, v 변수로 정점, 간선, 시작할 정점의 번호를 받은 뒤

matrix 변수를 만들어서 2차원 배열을 만들어줬어요.

​

다음으로 for문을 이용해서 간선의 수만큼

a, b 변수로 정수를 입력받고 그것을 위에 만들어둔 2차원 배열에 1로 치환해서 넣어주면

0 1 2 3 4

0[[0, 0, 0, 0, 0],

1 [0, 0, 1, 1, 1],

2 [0, 1, 0, 0, 1],

3 [0, 1, 0, 0, 1],

4 [0, 1, 1, 1, 0]]

위와 같이 2차원 배열이 완성되요.

여기서 조심해야 할 점은 기계는 무조건 0부터 세기 때문에 0도 생각해서 2차원 배열을 만들어줘야합니다👏

​

다음으로 이제 DFS와 BFS가 각각 어떻게 나오는지 알기 위한 함수를 정의해줬는데

아직 저도 정확히 이해하기 힘들더라구요...😭

​

그래도 이해한만큼 풀이를 하자면, 먼저 방문하는 정점을 알기 위해서 visit 변수로

[0, 0, 0, 0, 0]

위와 같이 1차원 배열을 만들고 시작했어요.

​

그리고 탐색을 시작할 정점의 번호인 v를 인자(argument)로

DFS(깊이 우선 탐색)은 처음 정점의 번호를 1로 초기화 하고

for문을 통해 1부터 4까지 돌려주면서 if문을 돌리면

visit[i] == 0은 위 1차원 배열이 다 0이니 참이고

결국 matrix[v][i] == 1을 판별하는 것이 중요하게 되요.

이때 2차원 배열로 만들어둔 것이 입력되고 기계는 이 2차원 배열에 1이 있는 것을 판단해서

1 → 2 → 4 → 3 순서로 출력이 되요.

​

다음으로 BFS(너비 우선 탐색)은 큐의 특성을 이용해서 넣는 순서대로 pop하는 방법을 이용했어요.

DFS와 다르게 방문한 점을 0으로 표시하고 들려야 할 정점을 큐에 저장하면서

while문으로 반복해주고 그 안에서 for문으로 DFS처럼 1부터 4까지 돌려주며

if문으로 matrix[v][i] == 1을 판별해서 큐에 append(추가)하는 식으로 해주면

1 → 2 → 3 → 4 순서로 출력되면서 끝이 납니다...😂

​

DFS와 BFS의 결과를 보고 다시 풀이 맨 위에 올린 사진을 보면 좀 더 이해가 되실거에요👏

저도 다시 보면서 복습을 열심히 해야겠네요..!! 풀면서 아직도 많이많이 부족하다고 느꼈습니다😥

처음부터 다 잘할 수 없듯이.. 좀 더 노력해야겠습니다💪

​

자세한 코드가 궁금하신 분들은 아래 GitHub 참고해주세요🙏

wook2124/Algorithm

최종 소스코드