DFS와 BFS

last update: 2021.09.08.WED

1260 DFS와 BFS, Silver 2

Memory 33644KB, Time 124ms

아래 에러 케이스와 비교하면 가장 큰 차이는,
성공 케이스는 visited를 리스트로 설정했고 실패 케이스는 딕셔너리로 두었다는 점이다.
딕셔너리가 접근이 더 빠를 것 같아서 사용했지만 결과적으로는 실패였다. 정석대로 리스트를 쓰는 편이 좋을 것 같다.

import sys
from collections import deque


def dfs(start):
    visited = {}
    stack = [start]
    while stack:
        n = stack.pop()
        if n not in visited and graph.get(n) == None:
            visited[n] = 1
            print(n, end="")
        elif n not in visited and graph.get(n) != None:
            visited[n] = 1
            print(n, end=" ")
            temp = sorted(graph[n], reverse=True)
            for num in temp:
                if num not in visited:
                    stack.append(num)

    return visited


def bfs(start):
    visited = {}
    q = deque([start])
    while q:
        v = q.popleft()
        if v not in visited and graph.get(v) == None:
            visited[v] = 1
            print(v, end="")
        elif v not in visited and graph.get(v) != None:
            visited[v]=1
            print(v, end=" ")
            temp = sorted(graph[v])
            for num in temp:
                if num not in visited:
                    q.append(num)


    return visited

n, m, start = map(int, sys.stdin.readline().split())
graph = {}
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a == b:
        pass
    if a in graph:
        graph[a].add(b)
    else:
        graph[a] = {b}
    if b in graph:
        graph[b].add(a)
    else:
        graph[b] = {a}

dfs(start)
print()
bfs(start)

런타임 에러를 많이 겪었다. 에러 코드 중 하나를 백업해둔다.

import sys
from collections import deque


def dfs(start):
    visited = {}
    stack = [start]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited[n] = 1
            print(n, end=" ")
            if len(graph[n]) != 0:
                temp = sorted(graph[n], reverse=True)
                for num in temp:
                    if num not in visited:
                        stack.append(num)


    return visited


def bfs(start):
    visited = {}
    q = deque([start])
    while q:
        v = q.popleft()
        if v not in visited:
            visited[v]=1
            print(v, end=" ")
            if len(graph[v]) != 0:
                temp = sorted(graph[v])
                for num in temp:
                    if num not in visited:
                        q.append(num)


    return visited

n, m, start = map(int, sys.stdin.readline().split())
graph = {}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a == b:
        pass
    if a in graph:
        graph[a].add(b)
    else:
        graph[a] = {b}
    if b in graph:
        graph[b].add(a)
    else:
        graph[b] = {a}

dfs(start)
print()
bfs(start)