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

DFS와 BFS

2 초

128 MB

202354

74509

44220

35.842%

문제

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

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

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

---

N,M,V = map(int,input().split())

#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]     # 인덱스 번호대로 사용하려고 (정점의 개수)+1 함
for i in range(M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1           # a와 b를 연결해주는 간선을 표시함

#방문 리스트 행렬
visited1 = [0]*(N+1)        # (정점의 개수)+1 만큼 0으로 채운 리스트 -> DFS용
visited2 = visited1.copy()  # (정점의 개수)+1 만큼 0으로 채운 리스트 -> BFS용

#dfs 함수 만들기
def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:   # V가 i번과 간선으로 연결되어 있는데, 아직 방문을 안 했으면 방문
            dfs(i)
# 이어지는 순서대로 방문한다

#bfs 함수 만들기
def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문한 순서대로 출력
        print(V, end = ' ')
        for i in range(1, N+1):
            if(visited2[i] == 0 and graph[V][i] == 1):  # V가 i번과 간선으로 연결되어 있는데, 아직 방문을 안 했으면 방문
                queue.append(i)                         # 방문한 순서대로 queue에 넣음.
                visited2[i] = 1                         # 방문처리함으로써 이후에 또다시 큐에 넣지 않게 함.
# V와 연결되어있는 모든 노드를 방문하고,
# 방문한 순서대로 또 연결되어있는 모든 노드를 방문한다.

dfs(V)
print()
bfs(V)

 

깊이우선탐색인 DFS는 방문해서 이어지는대로 방문하고

 

너비우선탐색인 BFS는 방문한 하나의 노드와 이어지는 모든 노드를 방문한 후에

방문했던 순서대로 각각의 노드와 이어지는 모든 노드를 방문한다.

 

DFS, BFS를 사용하려면 0은 만들지만 사용하지 않는다.

그러기 위해 N+1로 2차원의 리스트 공간을 만든다.

 

그리고 각각의 노드가 이어진 것을 표현해주고

 

노드 방문을 했는지 안 했는지 체크할 리스트도 만들어준다.

 

마지막으로 DFS는 이어지는 순서대로 방문하도록,

BFS는 이어진 노드들은 한 번에 방문하도록

함수형으로 코드를 짠다.

---

예전에 나동빈 강의에서는 이렇게 짰다.

# DFS 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문처리. 방문하면 True
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:  # not False = True, visited[i]가 False(미방문)이면 dfs 재귀호출
            dfs(graph, i , visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],     # index대로 직관적으로 사용하기 위해 0은 비워놓는다.
    [2,3,8],    # 여기 입력된 순서대로 진행된다 2 -> 3 -> 8
    [1,7],      # 1 -> 7
    [1,4,5],    # 1 -> 4 -> 5 ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트) 미방문을 False로 함
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기. 선입선출
        v = queue.popleft()    # v는 삽입된 순서대로 천천히 빠진다.
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]: # 해당 v에 들어있는 모든 원소를 queue에 삽입한다. 그리고 방문한 것으로 친다.
            if not visited[i]: # 여기서 방문하지 않은 노드를 모두 큐에 넣는다.
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],     # index대로 직관적으로 사용하기 위해 0은 비워놓는다.
    [2,3,8],    # 여기 입력된 순서대로 진행된다 2 -> 3 -> 8
    [1,7],      # 1 -> 7
    [1,4,5],    # 1 -> 4 -> 5 ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트) 미방문을 False로 함
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6