[백준/실버2] 1260번 DFS와 BFS | 파이썬 Python

문제

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

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

 

입력

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

 

출력

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

 

예제

 

나의 풀이 (실패)

import sys
from collections import deque
input = sys.stdin.readline

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

for _ in range(M):
    a, b = map(int, input().split())
    node.append((a, b))

def DFS(start):
    visited = [False] * (N + 1)

    visited[start] = True
    stack = [start]

    while stack:
        now = stack.pop()
        print(now, end=" ")

        temp = []

        for a, b in node:
            if a == now and not visited[b]:
                temp.append(b)
            elif b == now and not visited[a]:
                temp.append(a)
        
        if temp:
            stack.append(min(temp))
            visited[min(temp)] = True

def BFS(start):
    visited = [False] * (N + 1)
    
    visited[start] = True
    queue = deque([start])

    while queue:
        now = queue.popleft()
        print(now, end=" ")

        temp = []

        for a, b in node:
            if a == now and not visited[b]:
                temp.append(b)
                visited[b] = True
            elif b == now and not visited[a]:
                temp.append(a)
                visited[a] = True

        queue.extend(sorted(temp))

DFS(V)
print()
BFS(V)

• 각각 스택과 큐를 이용해서 풀었는데 예제 3개만 통과하고 제출 결과는 틀려서 실패했다.

 

다른 사람의 풀이1

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)]

visited1 = [False] * (N + 1)
visited2 = [False] * (N + 1)

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

def DFS(V):
    print(V, end=" ")
    visited1[V] = True
    
    for i in range(1, N+1):
        if not visited1[i] and graph[V][i]:
            visited1[i] = True
            DFS(i)

def BFS(V):
    visited2[V] = True
    queue = deque([V])

    while queue:
        V = queue.popleft()
        print(V, end=" ")

        for i in range(1, N+1):
            if not visited2[i] and graph[V][i]:
                queue.append(i)
                visited2[i] = 1

DFS(V)
print()
BFS(V)

• 그래프의 간선 구조를 2차원 리스트에 True, False 값으로 저장한다.
• DFS와 BFS 모두 visited[i] == False와 graph[V][i] == 1 조건을 동시에 충족할 때 다음 정점으로 이동한다.
• DFS 수행 결과는 재귀함수를 이용해 구한다.
  • 따로 종료 조건을 설정하지는 않았지만, visited의 모든 요소가 True가 되면(인덱스 0 제외) 재귀함수가 종료된다.
• BFS 수행 결과는 큐를 이용해 구한다.
  • 정점을 큐에 추가한 순서대로 이동한다.
  • 큐 안에 요소가 없다면, 즉 더 이상 이동할 정점이 없다면 반복문을 종료한다.

 

다른 사람의 풀이2

import sys
from collections import deque
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[] * (N + 1) for _ in range(N+1)]

visited1 = [False] * (N + 1)
visited2 = [False] * (N + 1)

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

for i in graph:
    i.sort()

def DFS(V):
    print(V, end=" ")
    visited1[V] = True
    
    for i in graph[V]:
        if not visited1[i]:
            visited1[i] = True
            DFS(i)

def BFS(V):
    visited2[V] = True
    queue = deque([V])

    while queue:
        V = queue.popleft()
        print(V, end=" ")

        for i in graph[V]:
            if not visited2[i]:
                queue.append(i)
                visited2[i] = 1

DFS(V)
print()
BFS(V)

• 2차원 리스트에 인접 정점 번호를 직접 저장한다.
  • 예를 들면 graph[1]에는 1번 정점과 연결된 정점들의 번호가 들어있다.
• for문을 실행할 때마다 N개의 모든 정점을 탐색했던 풀이 1번과 다르게, 2번 풀이는 딱 인접 정점들만 탐색한다.
  • "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"한다는 제한사항이 있기 때문에 그래프 안의 각 요소를 sort()하는 과정이 추가되었다.
  • 1번 풀이에서는 range(1, N+1)로 작은 수부터 순차적으로 탐색했기 때문에 sort()가 필요하지 않았다.
• if문 조건도 visited[i] == False인지만 확인하면 된다.
• 1번 풀이 방법에 비해 실행 시간이 거의 절반으로 줄어들었다.