07.22 TIL

 

오늘 푼 문제는 DFS와 BFS 를 동시에 출력하게한 문제를 풀었다.

import sys
from collections import deque
N, M, V = map(int, sys.stdin.readline().split()) # N = 정점의 개수, M = 간선의 개수, V = 탐색을 시작할 번호
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N+1): # 탐색 순서 유지를 위한 그래프 정렬
    graph[i].sort()

def my_dfs(graph, V):
    visited = list() # 방문한 노드를 담을 배열
    stack = list() # 정점과 인접한 방문 예정인 노드를 담을 배열

    stack.append(V) # 처음에는 시작 노드 담아주고 시작하기.

    while stack: # 더 이상 방문할 노드가 없을 때까지.
        node = stack.pop() # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            # stack.extend(graph[node]) # 해당 노드의 자식 노드로 추가
            stack.extend(reversed(graph[node]))

    print(*visited)
    return visited

def bfs(graph, V):
    visited = deque()  # 방문한 노드
    need_visit = deque()  # 방문할 노드

    need_visit.append(V)

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:  # 방문한 적이 없다면
            visited.append(node)  # 방문한 노드에 추가
            need_visit.extend(graph[node]) # 꺼낸 노드와 인접한 노드를 넣어줌

    print(*visited)
    return visited


my_dfs(graph, V)
bfs(graph,V)

 내가 짠 코드이다.

 

조금 많이 긴 것 같지만..... 그래도 푼게 어디냐 라 생각한다.

 

저 위 코드에서 내가 가장 중요하게 생각하는 부분은 

for i in range(1, N+1): # 탐색 순서 유지를 위한 그래프 정렬
    graph[i].sort()

 

이거라고 생각한다.

 

저 코드를 쓰지 않으니 어떤것은 출력이 맞게 나오지만, 어떤것은 출력이 제대로 나오지 않았는데 저걸 쓰니 바로 올바른 출력들이 나왔다.

 

 

내일은 이 문제를 가지고 TIL을 작성하겠다. 내일의 나 화이팅!