백준 - 1260 - DFS와 BFS [파이썬]

그래도 dfs bfs 앞에서 그림그려가면서 공부해서 나름의 자신감을 가지고 시작!!

https://jjrm.tistory.com/152

탐색 알고리즘 - DFS, BFS

1. 문제

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

1260번: DFS와 BFS

2. 이해 및 풀이

와 그래도 알고리즘은 이해해서 함수는 구현할 수 있겠는데, 문제는 입력값으로 인접리스트를 만드는 것이다.

그림으로는 쉽게 그려지는데

일단 워~워~ 워워

 

dfs(깊이 우선탐색)는

스택을 사용하고, 재귀로 구현!(하려고했으나, 재귀보단 그냥 반복문이 편한가보다..) 

그리고 dfs에서 작은 수부터 돌기 위해 reversed 사용(아는 척 아는 척)

 

bfs(너비 우선탐색)는

데크를 사용. 이때 탐색 시작 노드를 데크에 삽입하고 방문 처리(visited에 추가)

큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 데크에 삽입하고 꺼냈을 때 visited에 없으면 방문처리를 해준다

->이걸 마지막 노드에 갈 때까지 반복한다.

화나서 봤더니, 입력값을 잘못,,,, 넣었다... 파이참에서 한시간을 넘게 싸웠는데,, 아 허무해

 

크게 두가지 방식이 있는 거 같다.

visited를 비어있는 리스트로 두어 채우는 방식과 / visited를 디폴트값으로 false로 둔 다음에 요소가 나올 떄마다 true로 바꿔주는 방식

 

#. 내 풀이 (채우기)

from collections import deque
import collections

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

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

def bfs(graph, start):
    visited = []
    queue = collections.deque([start])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            if n in graph:
                queue.extend(graph[n])
    return visited

def dfs(graph, start):
    visited = []
    stack = [start]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                stack.extend(reversed(graph[n]))
    return visited

print(*dfs(graph, V))
print(*bfs(graph, V))

 

#. 다른사람풀이(false->true)

from collections import  deque

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

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

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()


visited = [False] * (n + 1)

def Dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            Dfs(graph, i, visited)

def Bfs(graph, v, visited):
    visited = [False] * (n + 1)
    queue = deque([v])
    visited[v] = True
    while queue:
        pop = queue.popleft()
        print(pop, end=' ')
        for i in graph[pop]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

Dfs(graph, v, visited)
print()
Bfs(graph, v, visited)

시간 너무 오래 걸림.. 모르게쒀여

오늘의 교훈 :  입력값을 제대로 쓰자 젭알.