[백준] 1260 DFS와 BFS (실버2)

문제요약

나의 코드 및 설명

from collections import deque

def dfs(c):
    visited[c] = 1 #현재 정점 방문 처리
    ans_dfs.append(c) #정답 리스트에 현재 정점 추가
    for n in graph[c]: #현재 정점과 연결된 다른 정점들 살펴보기
        if visited[n] == 0: #만약 다른 정점이 아직 방문하지 않았다면
            dfs(n) #다음 정점 방문

def bfs(s):
    queue = deque() #큐 생성
    queue.append(s) #큐에 현재(시작) 정점 추가
    visited[s] = 1 #현재 정점 방문처리
    ans_bfs.append(s) #정답 리스트에 현재 정점 추가

    while queue: #정점이 하나도 없을때까지 
        c = queue.popleft() #큐에 먼저 들어간 순으로 꺼낸다
        for n in graph[c]: #꺼낸 정점과 연결된 다른 정점들 살펴보기
            if visited[n] == 0: #만약 다른 정점이 아직 방문하지 않았다면
                queue.append(n) #큐에 다른 정점들 삽입
                ans_bfs.append(n) #정답 리스트에 다른 정점들 삽입
                visited[n] = 1 #다른 정점들 방문처리

n,m,v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

#오름차순 정렬
for i in range(1, n+1):
    graph[i].sort()


visited = [0] * (n+1)
ans_dfs = []
dfs(v)

visited = [0] * (n+1)
ans_bfs = []
bfs(v)

print(" ".join(map(str, ans_dfs)))
print(" ".join(map(str, ans_bfs)))

피드백

백트래킹 문제 연습을 조금 했더니 이제 DFS 문제는 조금씩 보이는 것 같다. BFS가 부족한 것 같아서 더 공부해야할 것 같다.