백준 1260번 DFS와 BFS

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

이 문제를 시작하기전 나는 알고리즘에 대한 개념은 어느정도 머리속에 박혀있다고 생각했지만

구현을 할 수 없는, 자신감이 완전 제로인 사람이였다.

DFS와 BFS는 그런사람에게 아주 적절한 문제라고 생각한다.

본인은 Python으로 구현했고

BFS를 구현할때 collections라이브러리의 deque을 사용했다.

먼저 문제를 읽어보면

DFS와 BFS를 모두 사용해서 탐색한 결과를 출력하는 프로그램이고
방문할 수 있는 정점이 여러개 인 경우, 정점번호가 작은 것 을 먼저 방문하고,
더이상 방문할 수 있는 점이 없는 경우 종료한다. 라고 되어있다.

작은 것을 먼저 방문하라고 조건이 나와있기 때문에 오름차순으로 정렬해야겠다는 생각이 들었다.

그리고 입력에서는
입력으로 주어지는 간선은 양방향이다 라는 부분에 주목했다.

DFS는 방문했던 노드를 담을 배열과 방문할 노드를 담을 스택을 처음에 선언해줬다. << 탐색을 시작할 정점의 번호 V를 넣어준다.
그리고 스택에 값들이 있는동안 계속 반복하는 반복문 안에
1. 스택에 담겨있는 노드를 빼서
2. 만약 노드가 방문했던 노드 배열에 없다면
3. 방문했던 노드 배열에 노드를 넣고
4. 스택에 노드의 간선에 닿아있는 다른 노드들을 저장하는데 이때 오름차순으로 정렬해서 저장.

그리고 방문했던 노드배열을 리턴해줬다.

def dfs(graph, start):
	visited = [] 
    stack = [start]
    
    while stack:
    	node = stack.pop() #1
        if node not in visited: #2
        	visited.append(node)
            stack.extend(sorted(graph[node], reverse=True))
    return visited

BFS는 DFS와 유사하지만 stack이 아닌 deque를 이용한 queue형식의 자료구조를 택했다.
똑같이 방문했던 노드를 담을 배열을 만든 뒤
방문할 노드를 담을 큐를 선언해주고 << 당연히 탐색을 시작할 정점의 번호 V를 넣어줬다.
큐에 값이 있는 동안
1.큐에서 노드를 꺼내서
2. 노드가 방문했던 노드배열에 없으면
3. 넣어주고
4. 노드와 간선으로 닿아있던 다른 노드들을 큐에 넣어준다.
마지막으로 방문했던 노드배열을 리턴.

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

이렇게 만든 뒤

메인 로직을 완성 했다.

N, M, V = map(int, input().split()) #띄어쓰기로 구분해서 int로 나눠 저장
graph = [[] for _ in range(N+1)] #리스트 컴프리헨션을 이용해서 정점의 개수 +1 만큼 만들기.

for _ in range(M) : #간선의 개수 만큼 반복
	a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) #양방향이기 때문에 서로 넣기
print(' '.join(map(str, dfs(graph, V)))) #띄어쓰기로 구분
print(' '.join(map(str, bfs(graph, V))))

~사소한 찐빠들~

bfs 만들때 while queue를 할거 stack으로 적어버려서 nameError를 경험.
print(' '.join())에서 int도 되는줄 알고 map(int,~) 적어버리다 typeError를 경험.
''.join()은 str타입만 들어와야한다.