[백준] 1260. DFS와 BFS

문제

고려해야 하는 반례

<채점 중 87%에서 런타임에러 발생>

1000 1 1
99 1000

반례에서 알아야 하는 부분

• 어떠한 간선도 존재하지 않는 노드가 존재한다. -> 해당 조건을 추가해줘야 한다.

import sys
from collections import deque

# 입력으로 들어온 간선 정보 저장
def makeGraph(points):
    graph = dict()
    for p in points:
    # 간선은 양방향이기 때문에 각각의 노드에 연결된 노드에 대한 정보를 추가해주어야 한다.
    # 모든 노드가 간선을 가지는 것이 아니다.
        if not p[0] in graph.keys():
            graph[p[0]] = []
        if not p[1] in graph.keys():
            graph[p[1]] = []
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])
    for g in graph:
        graph[g].sort()
    return graph

def dfs(graph, visited, v):
    visited[v] = True
    print(v, end=' ')
    if v in graph: # 반례를 통해 알아낸 조건 추가
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, visited, i)

def bfs(graph, visited, v):
    queue = deque([v])
    visited[v] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        if v in graph: # 반례를 통해 알아낸 조건 추가
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

def start():
    n, m, v = map(int, sys.stdin.readline().split())

    points = [list(map(int, sys.stdin.readline().split())) for i in range(m)]

    visited_dfs = [0] * (n+1)
    visited_bfs = [0] * (n+1)
    graph = makeGraph(points)
    dfs(graph, visited_dfs, v)
    print()
    bfs(graph, visited_bfs, v)

start()

매번 까먹는 부분

bfs 구현 시 queue가 필요한데, 파이썬에서는 deque와 Queue로 구현할 수 있다.

deque

• double-ended queue, 데이터 양방향 추가, 제거 가능

• deck 이라고 읽음

• thread-safe와 appends와 pops의 메모리 효율성 보장

• deque는 초기화해줄 때, 다음과 같이 deque([5])

from collections import deque

queue = deque([4]) # queue -> 4
queue.append(5) # queue -> 4 5
queue.append(6) # queue -> 4 5 6
queue.popleft() # 4, queue -> 5 6
queue.popleft() # 5, queue -> 6

queue.clear() # queue -> 

Queue

from queue import Queue

queue = Queue()

queue.put(4) # queue -> 4
queue.put(5) # queue -> 4 5
queue.put(6) # queue -> 4 5 6

queue.get() # 4, queue -> 5 6
queue.get() # 5, queue -> 6
queue.get() # 6, queue ->