백준 1260: DFS와 BFS (Python)

 

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

1260번: DFS와 BFS

 

from collections import deque

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

for i in range(m):
    data = input().split()
    graph[int(data[0])].append(int(data[1]))
    graph[int(data[1])].append(int(data[0]))

for i in range(n+1):
    graph[i].sort()

dfs_visited = [False] * (n+1)
bfs_visited = [False] * (n+1)

def dfs(dfs_visited, v):
    dfs_visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not dfs_visited[i]:
            dfs(dfs_visited, i)

def bfs(bfs_visited, v):
    bfs_visited[v] = True
    queue = deque([v])

    while queue:
        q = queue.popleft()
        print(q, end=' ')

        for i in graph[q]:
            if not bfs_visited[i]:
                queue.append(i)
                bfs_visited[i] = True

dfs(dfs_visited, v)
print()
bfs(bfs_visited, v)

 

그래프 번호가 1번부터 시작하기 때문에 리스트 크기를 편하게 n+1로 잡았다! (인덱스 0은 비어있음)

노드번호별로 그래프에 연결된 노드 넣어주고 그 안에서 정렬한 다음에 각각 dfs, bfs를 돌려주었다

아무리 봐도 틀린게 없어보이는데 자꾸 실패해서 화나서 밥 먹고 쉬다가 왔는데

알고 보니까 멍청하게 그래프 정렬할 때 포문을 n+1로 돌려야 하는데 n으로 돌려서 정렬이 다 안되어있었음,,

꼼꼼하게 확인해보자,,