0304_백준 1260번 : DFS와 BFS (개념 알고 익숙해지기)

*출처 : 백준 1260번 문제 

 

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

1260번: DFS와 BFS

 

# DFS와 BFS 코드

 

1차 풀이 : 다른 사람들의 풀이와 비교했을 때 시간이 더 오래 걸린다는 것을 파악. 시간 단축 필요.

 

- 맨 처음 DFS를 풀었을 때는 노드와 엣지를 표현할 때 2차원 배열을 사용했는데, 이게 정답은 나왔는데 시간 초과가 떴던 거 같다. 아무래도 2차원 배열은 모든 노드들의 관계를 살펴보기 때문에 시간 소요가 더 컸을 것이다. 

- 그 다음 인접리스트만 구성해서 풀이했는데, 함수 내부에 불필요한 과정을 줄여야 계산 시간이 줄 것 같다. 특히 not in, append, pop 가 시간 소요가 크다고 들었다. 

 

def dfs(v):
    stack = []
    stack.append(v)
 
    while stack:
        #dfs는 pop으로 뒤에서 부터 가져옴
        current = stack.pop()
        new_adj = adj[current]
        new_adj.sort()
        new_adj.reverse()
        for neighbor in new_adj:
            if neighbor not in visited:
                stack.append(neighbor)
        if current not in visited:
            visited.append(current)
 
def bfs(v):
    queue = []
    queue.append(v)
 
    while queue:
        current = queue.pop()
        new_adj = adj[current]
        new_adj.sort()
        for neighbor in new_adj:
            if neighbor not in visited:
                queue.insert(0, neighbor)
        if current not in visited:
            visited.append(current)
 
# 인풋
n, m, v = map(int,input().split())
adj = [[] for _ in range(n+1)]
visited = []
result = []
 
# 인접리스트
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
 
dfs(v)
print(*visited)
visited = []
bfs(v)
print(*visited)

 

2차 풀이 : 백준 풀이번호 12580200 코드 활용

- 찾아보니 input() 대신 sys외장 라이브러리 호출 후 sys.stdin.readline() 을 사용하면 시간 단축된다고 함

- stack 과 queue에 하나씩 append 하지 않고 리스트 통으로 넣어주었다. (extend 사용해도 됨)

- 오름차순 후 역순 정렬 시 => 리스트. sort(reverse =True)

 

import sys
N, M, V = map(int, sys.stdin.readline().strip().split())
edge = [[] for _ in range(N+1)]
 
for _ in range(M):
    n1, n2 = map(int, sys.stdin.readline().strip().split())
    edge[n1].append(n2)
    edge[n2].append(n1)
 
# 인접리스트 정렬 후 역순
for e in edge:
    e.sort(reverse=True)
 
def dfs():
    d_visit = []
    stack = [V]
    d_check = [0 for _ in range(N+1)]
    while stack:
        v1 = stack.pop()
        if not d_check[v1]:
            d_check[v1] = 1
            d_visit.append(v1)
            stack += edge[v1]
            # edge[v1]은 리스트 형태
    return d_visit
 
def bfs():
    b_visit= []
    queue = [V]
    b_check = [0 for _ in range(N+1)]
    # 시작점 다시 오지 않게 1 처리
    b_check[V] = 1
    while queue:
        v2 = queue.pop()
        b_visit.append(v2)
        for i in reversed(edge[v2]):
            # 작은 숫자부터 뽑아야 하니 다시 역순
            if not b_check[i]:
                b_check[i] = 1
                queue = [i] + queue
                # 리스트 안에 추가
    return b_visit
 
print(' '.join(map(str, dfs())))
print(' '.join(map(str, bfs())))

 

 

 

#개념, 간단히 정리 

DFS (깊이 우선 탐색) : 임의의 한 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전 탐색하는 방법
- 깊게 탐색, 모든 노드를 방문, 검색 속도는 BFS 보다 느림, 한 방향으로 갈 수 있을 때까지 이동 후 더 이상 갈 수 없게 되면 가장 가까운 분기점으로 돌아와서 다시 탐색하는 방법
- 재귀 알고리즘의 형태, 방문한 노드 반드시 확인 (그렇지 않으면 무한루프), 후입 선출

BFS (넒이 우선 탐색) : 한 노드에서 시작해 모든 노드들을 방문하는 방법
- 넓게 탐색, 시작점에서 가까운 것부터 단계적으로 나아가 탐색(1-2-3'''단계), 최단 경로나 임의의 경로 찾을 때 사용,
- DFS 보다 더 복잡, 재귀X, 큐(QUEUE)를 사용해 방문한 노드 반드시 확인 (그렇지 않으면 무한루프), 선입선출

 

 

=> 아래는 DSF와 BFS 개념과 과정을 이해하기 위해 참고한 유튜브 영상 

 

*출처 : https://www.youtube.com/watch?v=BLc3wzvycH8&t=164s

 

출처 : https://www.youtube.com/watch?v=0v3293kcjTI&t=94s

 

 

=> 추가적으로 알아둘 부분, collection과 deque 쓰는 방법 ( +popleft)