DFS와 BFS의 개념을 총정리할 수 있어서 좋았던 문제!

1. 내 풀이: 성공

import sys
from collections import deque
input = sys.stdin.readline

n, m, v= map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# dfs
resultDFS = []
def dfs(k):
    resultDFS.append(k)
    visited[k] = 1
    graph[k].sort()
    for i in graph[k]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)
dfs(v)

# bfs
resultBFS = []
visited = [0]*(n+1)
visited[v] = 1
Q = deque()
Q.append(v)
while Q:
    current = Q.popleft()
    resultBFS.append(current)
    for i in graph[current]:
        if visited[i] == 0:
            visited[i] = 1
            Q.append(i)

print(" ".join(map(str, resultDFS)))
print(" ".join(map(str, resultBFS)))

간만에 보는 마쟈씁니댜 ,,,
사실 DFS랑 BFS는 풀이 템플릿이 정해져있어서 거기에 맞춰서 풀면 되었다.
풀이 템플릿과 관련해서는 이전 포스팅 참고!

2. 다른 풀이

from collections import deque

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

graph = [[False] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (N + 1)  # dfs의 방문기록
visited2 = [False] * (N + 1)  # bfs의 방문기록


def bfs(V):
    q = deque([V])  # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다
    visited2[V] = True  # 해당 V 값을 방문처리
    while q:  # q가 빌때까지 돈다.
        V = q.popleft()  # 큐에 있는 첫번째 값 꺼낸다.
        print(V, end=" ")  # 해당 값 출력
        for i in range(1, N + 1):  # 1부터 N까지 돈다
            if not visited2[i] and graph[V][i]:  # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
                q.append(i)  # 그 i 값을 추가
                visited2[i] = True  # i 값을 방문처리


def dfs(V):
    visited1[V] = True  # 해당 V값 방문처리
    print(V, end=" ")
    for i in range(1, N + 1):
        if not visited1[i] and graph[V][i]:  # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
            dfs(i)  # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)


dfs(V)
print()
bfs(V)

풀이 출처: https://ji-gwang.tistory.com/291

사실 풀이는 거의 유사하고 ㅎㅎ...
이 풀이를 가져온 이유는

dfs(V)
print()
bfs(V)

이 부분 때문이다.
처음에 나도 이 풀이처럼 각 함수에 곧바로 print 문을 찍을 수 있도록 했는데 end=" "를 쓰게 되니 전부 답이 붙여져 나왔다.
이럴 때 줄바꿈을 하려면 딱 하나의 print만 쓰면 되는 구나...를 깨달을 나 ... ^^

3. 마치며

그래프 재밌당 ~~~
앞으로 또 백준 푸는 맛이 날 것 같다!