[BOJ] 파이썬 - 1260 DFS와 BFS

문제 링크 : https://www.acmicpc.net/problem/1260

파이썬 코드

from collections import deque
import sys

N,M,V=map(int,sys.stdin.readline().split())

graph=dict()

for i in range(1,N+1):
    graph[i]=[]
#시작점에 연결된 간선이 없는 경우가 있기때문에, 모든 노드를 key로 만들어줌

for i in range(M):
    a,b=map(int,sys.stdin.readline().split())
    if a not in graph:
        graph[a]=[b]
    elif b not in graph[a]:
        graph[a].append(b)
    if b not in graph:
        graph[b]=[a]
    elif a not in graph[b]:
        graph[b].append(a)


def dfs(graph,root):
    visited = [0] * N
    result=[]
    stack=[root]

    while stack:
        n=stack.pop()
        if visited[n-1]==0:
            visited[n-1]=1
            if n not in result:
                result.append(n)
                stack+=sorted(list(set(graph[n])-set(result)),reverse=True)
                #스택은 뒤에서부터 pop되니까 reverse해줌
                #set(graph[n])-set(result)하면, 오름차순으로 정렬돼서, reverse해서 stack에 삽입하면 작은 수부터 뺄 수 있음
        else:
            continue

    return result

def bfs(graph,root):
    visited = [0] * N
    result=[]
    queue=deque([root])

    while queue:
        n=queue.popleft()
        if visited[n-1]==0:
            visited[n-1]=1
            if n not in result:
                result.append(n)
                queue+=sorted(list(set(graph[n])-set(result)))
        else:
            continue

    return result

print(*dfs(graph,V),sep=' ')
print(*bfs(graph,V),sep=' ')

딕셔너리를 통해 인접리스트를 구현하여 그래프를 구현했다.

visited를 통해 방문한 정점을 체크하여 불필요한 if문을 돌지 않도록 해서 시간을 단축했다.

visited를 사용하지 않았을 경우 284ms
visited를 사용했을 경우 156ms 로 시간 차이가 꽤 났다.

dfs,bfs 각각 stack과 queue를 방문하여 노드를 pop한다.
해당 node를 방문한 적이 없다면 vistied를 1로 체크해주고
result에 추가(방문)해준다.
그리고 해당 노드에 연결된 노드들을 stack과 queue에 추가하여 탐색을 계속 진행한다.

유의할 점
<정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문>
<시작점에 연결된 간선이 없는 경우>- 이 경우를 고려하지 않아서 처음엔 런타임 에러가 떴다.