[백준 BOJ] 1260번 DFS와 BFS (파이썬 Python)

문제 설명

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

 

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,

더 이상 방문할 수 있는 점이 없는 경우 종료한다.

 

정점 번호는 1번부터 N번까지이다.

 

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

 

 

 

 

문제 풀이

알고리즘 문제풀이(1)의 그래프 단계 중 첫번째 문제.

 

dfs는 재귀로, bfs의 queue로 구현하는 것이 일반적이라고 한다.

 

 

기본적인 개념조차 없어 답을 봐도 이해가 어려웠다.

dfs는 계속 따라 내려가면 되는데, bfs는 어떻게 진행되는지 이해하기까지 시간이 좀 걸렸다.

 

 

입력 1에 따른 그래프 모양 (https://csacademy.com/app/graph_editor/)

 

 

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

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

graph = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

visited1 = [0]*(n+1) # dfs의 방문기록
visited2 = [0]*(n+1) # bfs의 방문기록

def dfs(v):
    visited1[v] = 1
    print(v, end=' ')
    for i in range(1, n+1):
        # 만약 i값을 방문하지 않았고, V와 연결이 되어 있다면
        if not visited1[i] and graph[v][i]:
            dfs(i)  # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)

def bfs(v):
    q = deque([v])
    visited2[v] = 1
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i]:
                q.append(i)
                visited2[i] = 1

dfs(v)
print()
bfs(v)

 

 

그래프 입력

graph = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

 

최초 0 (False)으로 채워진 2차원 리스트를 생성한다.

범위는 이후 인덱스 접근의 편의를 위해 (n+1)로 설정한다.

 

 

아래 for문은 그래프를 연결한다.

 

입력으로 주어진 (1, 2), (1, 3), (1, 4), (2, 4), (3, 4)를 a, b로 받아

해당 부분을 연결되었다는 의미로 1 (True)로 입력한다.

(주어진 그래프는 연결 방향의 구분이 없는 무방향 그래프이기 때문에 (a, b), (b, a)로

양 방향 모두 연결되었다는 것을 표현한다.)

 

 

 

 

 

 

 

 

 

참고 및 출처

문제 출처: https://www.acmicpc.net/problem/1260

정답코드: https://ji-gwang.tistory.com/291

 

(1) 알고리즘 문제풀이(PS) 시작하기

https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0