백준 1260 DFS와 BFS Python

문제설명

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

제한사항

• N(1 ≤ N ≤ 1,000)
• M(1 ≤ M ≤ 10,000)

입력

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

출력

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

예제

---

이 문제의 key 포인트

-> 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

-> 입력으로 주어지는 간선은 양방향이다.

위 두 조건을 고려하면 DFS와 BFS 기본지식으로 풀 수 있는 문제이다.
다른 사람들은 쉽게 풀 수 있다고 써놨는데 난.. 쉽게풀지 못했다..

반례참고: https://www.acmicpc.net/board/view/24356

---

자료구조 및 알고리즘: BFS, DFS

---

문제풀이

첫번째 풀이

코드(틀린코드, 11%에서 틀렸습니다)

import sys
from collections import deque
input = sys.stdin.readline
N, M, V = map(int, input().split())

graph = []
for i in range(M):
    temp = list(map(int, input().split()))
    graph.append(temp)
graph.sort()

# DFS
visited_dfs = [True] + [False] * (N)
result_dfs = []
def DFS(graph, v): 
    global visited_dfs

    # 현재노드 방문처리
    visited_dfs[v] = True
    # 현재 노드 저장
    result_dfs.append(v)
    for i in range(M):
        if graph[i][0] == v and visited_dfs[graph[i][1]] == False:
            DFS(graph, graph[i][1])
        elif graph[i][1] == v and visited_dfs[graph[i][0]] == False:
            DFS(graph, graph[i][0])

# BFS
visited_bfs = [True] + [False] * (N)
result_bfs = []
def BFS(graph, v):
    global visited_bfs
    
    # 현재 노드를 방문처리
    queue = deque([v])
    visited_bfs[v] = True  
    while queue:
        # 큐에서 원소 하나를 뽑아 저장
        v = queue.popleft()
        result_bfs.append(v)
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 + 방문처리
        for i in range(M):
            if graph[i][0] == v and visited_bfs[graph[i][1]] == False:
                queue.append(graph[i][1])
                visited_bfs[graph[i][1]] = True 
            elif graph[i][1] == v and visited_bfs[graph[i][0]] == False:
                queue.append(graph[i][0])
                visited_bfs[graph[i][0]] = True 

DFS(graph, V)
BFS(graph, V)

print(*result_dfs)
print(*result_bfs)

반례1

6 8 1
1 6 
6 2 
2 4 
4 3 
3 5 
5 1 
5 6 
2 3
----
1 5 3 2 4 6 
1 5 6 3 2 4

내 답

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

입력에서 [1, 6], [5, 1] 이 있으므로 노드 1에 연결된 노드는 5, 6이고, 작은 노드부터 방문해야 하므로 6번 노드보다 5번 노드를 먼저 방문해야 한다.

---

두번째 풀이

코드(틀린 코드, 88%에서 틀렸습니다)

import sys
from collections import deque
input = sys.stdin.readline
N, M, V = map(int, input().split())
graph = []
for i in range(M):
    temp = list(map(int, input().split()))
    if temp[0] > temp[1]:
        graph.append(temp[::-1])
    else:
        graph.append(temp)

graph.sort()

# DFS
visited_dfs = [True] + [False] * (N)
result_dfs = []
def DFS(graph, v): 
    global visited_dfs
    
    # 현재노드 방문처리
    visited_dfs[v] = True
    # 현재 노드 저장
    result_dfs.append(v)
    for i in range(M):
        if graph[i][0] == v and visited_dfs[graph[i][1]] == False:
            DFS(graph, graph[i][1])
        elif graph[i][1] == v and visited_dfs[graph[i][0]] == False:
            DFS(graph, graph[i][0])
                
# BFS
visited_bfs = [True] + [False] * (N)
result_bfs = []
def BFS(graph, v):
    
    global visited_bfs
    
    queue = deque([v])
    # 현재 노드를 방문처리
    visited_bfs[v] = True  
    
    while queue:
        # 큐에서 원소 하나를 뽑아 저장
        v = queue.popleft()
        result_bfs.append(v)
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 + 방문처리
        for i in range(M):
            if graph[i][0] == v and visited_bfs[graph[i][1]] == False:
                queue.append(graph[i][1])
                visited_bfs[graph[i][1]] = True 
            elif graph[i][1] == v and visited_bfs[graph[i][0]] == False:
                queue.append(graph[i][0])
                visited_bfs[graph[i][0]] = True 
DFS(graph, V)
BFS(graph, V)
       
print(*result_dfs)
print(*result_bfs)

반례2

1000 1 1
99 1000
----
1
1

내 답

1 99 1000

1 99 1000

시작 노드와 어떠한 간선도 존재하지 않을 경우

99와 1000 사이에만 간선이 있고 탐색을 시작하는 노드는 1이면 노드 1번 이외에 더 탐색할 수 있는 노드가 없는 것이다. 이 처리를 해줘야한다.

---

세번째 풀이

코드(완성 코드, 맞았습니다!!, 2764ms)

# BOJ 1260 BFS와 DFS
# 2764ms
# 33452KB

import sys
from collections import deque
input = sys.stdin.readline
N, M, V = map(int, input().split())
graph = []
for i in range(M):
    temp = list(map(int, input().split()))
    graph.append(temp)

# 한 노드에 여러 노드가 있을 때, 숫자가 작은 노드 먼저 탐색해야함 ->  정렬
graph.sort(key=lambda x:(min(x), max(x)))

# DFS
visited_dfs = [True] + [False] * (N)
result_dfs = []

def DFS(graph, v): 
    global visited_dfs

    # 현재노드 방문처리
    visited_dfs[v] = True
    # 현재 노드 저장
    result_dfs.append(v)

    # 양방향 간선 고려
    for i in range(M):
        if graph[i][0] == v and visited_dfs[graph[i][1]] == False:
            DFS(graph, graph[i][1])
        elif graph[i][1] == v and visited_dfs[graph[i][0]] == False:
            DFS(graph, graph[i][0])
                
# BFS
visited_bfs = [True] + [False] * (N)
result_bfs = []
def BFS(graph, v):
    global visited_bfs
    
    queue = deque([v])
    # 현재 노드를 방문처리
    visited_bfs[v] = True  
    
    while queue:
        # 큐에서 원소 하나를 뽑아 저장
        v = queue.popleft()
        result_bfs.append(v)
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 + 방문처리
        for i in range(M):
            if graph[i][0] == v and visited_bfs[graph[i][1]] == False:
                queue.append(graph[i][1])
                visited_bfs[graph[i][1]] = True 
            elif graph[i][1] == v and visited_bfs[graph[i][0]] == False:
                queue.append(graph[i][0])
                visited_bfs[graph[i][0]] = True 

DFS(graph, V)
BFS(graph, V)

print(*result_dfs)
print(*result_bfs)

문제를 풀고나서 다른 사람들의 채점현황을 보니 80ms까지 나온 경우도 많은데 내 코드는 2764ms가 나오는 것으로 보아 for문을 돌면서 양방향을 고려하는 부분에서 효율성을 많이 깎아먹었다고 생각했다. 

다른 사람의 풀이를 참고해 효율적인 코드를 만들어보았다.

 

네번째 풀이

코드(완성 코드, 맞았습니다!!, 80ms)

# BOJ 1260 BFS와 DFS
# 80ms
# 32280KB
# 처음에 연결된 노드를 그래프로 만들어놓으면 양방향 간선인것과 
# 작은 노드부터 탐색하는 과정을 따로 처리해주지 않아도 됨
# BFS 구현할 때 deque를 쓰는 것보다 list를 쓰는 게 더 효율적

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]
# 각 노드에 연결된 노드들을 정리
for _ in range(M):
	u, v = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
# 연결된 노드들을 정렬 -> 작은 노드부터 탐색하도록
for i in graph:
	i.sort()
# DFS -> 재귀
visited_dfs = [False] * (N + 1)
result_dfs = []
def DFS(graph, v):
    # 현재 노드 방문처리
	result_dfs.append(v)
	visited_dfs[v] = True
    # 현재 노드에 연결되어 있으면서 방문하지 않은 노드 방문
	for i in graph[v]:
		if not visited_dfs[i]:
			DFS(graph, i)

# BFS -> 큐
visited_bfs = [False] * (N + 1)
queue = []
result_bfs = []
def BFS(graph, v):
    # 현재 노드 큐에 넣고 방문처리
	queue.append(v)
	visited_bfs[v] = True 
    # 큐가 비지 않을 때까지
	while queue:
        # 큐에서 pop
		node = queue.pop(0)
		result_bfs.append(node)
        # 현재 노드에 연결되어있고 방문하지 않은 노드 큐에 삽입, 방문처리
		for i in graph[node]:
			if not visited_bfs[i]:
				queue.append(i)
				visited_bfs[i] = True
	
DFS(graph, V)
BFS(graph, V)
print(*result_dfs)
print(*result_bfs)

BFS 함수를 구현할 때 deque을 사용했을 때보다 그냥 list를 사용해서 구현한게 약 20ms정도 더 빨랐다.