[BOJ] 백준 1260 파이썬 - DFS와 BFS

문제 출처 :

1260번: DFS와 BFS

 

기본적인 DFS 와 BFS를 이용해 방문하는 노드를 순서대로 정렬하는 문제 입니다.

 

<그래프 구현 코드>

n, m, v = map(int, input().split())

dic = {}
for i in range(n):
    dic[i+1] = set()    # 각각의 간선에 연결된 노드 표시
for j in range(m):
    a, b = map(int, input().split())
    dic[b].add(a)
    dic[a].add(b)       # 서로가 서로의 하위 노드 이기 때문에 두개 모두에 추가

for i in range(1, n+1):
    dic[i] = sorted(dic[i])     # 방문할 노드가 여러개이면 작은 순서부터 방문한다 했으므로 sort 해줌

 

<DFS 구현 코드>

def dfs(start):
    if len(visitedDfs) == 0:
        # 첫번째 노드는 무조건 방문한 것 이므로 추가(for 문 안으로 들어가면 연결된게 없을때 오류남)
        visitedDfs.append(start)
    for i in dic[start]:
        if i not in visitedDfs:     # 상위 노드와 연결된 하위 노드가 방문된적이 없으면
            visitedDfs.append(i)
            dfs(i)      # 재귀함수로 계속 돌려줌

 

<BFS 구현 코드>

from collections import deque
queue = deque()     # bfs 할때 dequeue를 수월하게 해주기 위해 deque 선언


def bfs(start):
    queue.append(start)     # 연결된 하위노드의 너비에 해당하는 노드들을 추가
    visitedBfs.append(start)    # dfs와 마찬가지로 첫번째는 무조건 방문
    while queue:
        a = queue.popleft()     # 앞에서부터 순서대로 pop, 이미 sort됐기 때문에 크기 고려 안해줘도 됨
        for x in dic[a]:    # 상위노드와 연결된 하위노드 중에서
            if x not in visitedBfs:     # 방문 된적이 없다면
                queue.append(x)     # 작업열에 추가
                visitedBfs.append(x)    # 방문된 노드에 추가

 

<답 도출 코드>

dfs(v)
bfs(v)
print(*visitedDfs)
print(*visitedBfs)  # 리스트 형태가 아닌 노드의 번호만 출력해야 하므로 분해하여 출력

 

<전체 정답 코드>

from collections import deque
n, m, v = map(int, input().split())

visitedDfs = []
visitedBfs = []     # visited 리스트 초기화 안하려고 두개 선언
dic = {}
for i in range(n):
    dic[i+1] = set()    # 각각의 간선에 연결된 노드 표시
for j in range(m):
    a, b = map(int, input().split())
    dic[b].add(a)
    dic[a].add(b)       # 서로가 서로의 하위 노드 이기 때문에 두개 모두에 추가

for i in range(1, n+1):
    dic[i] = sorted(dic[i])     # 방문할 노드가 여러개이면 작은 순서부터 방문한다 했으므로 sort 해줌


def dfs(start):
    if len(visitedDfs) == 0:
        # 첫번째 노드는 무조건 방문한 것 이므로 추가(for 문 안으로 들어가면 연결된게 없을때 오류남)
        visitedDfs.append(start)
    for i in dic[start]:
        if i not in visitedDfs:     # 상위 노드와 연결된 하위 노드가 방문된적이 없으면
            visitedDfs.append(i)
            dfs(i)      # 재귀함수로 계속 돌려줌


queue = deque()     # bfs 할때 dequeue를 수월하게 해주기 위해 deque 선언


def bfs(start):
    queue.append(start)     # 연결된 하위노드의 너비에 해당하는 노드들을 추가
    visitedBfs.append(start)    # dfs와 마찬가지로 첫번째는 무조건 방문
    while queue:
        a = queue.popleft()     # 앞에서부터 순서대로 pop, 이미 sort됐기 때문에 크기 고려 안해줘도 됨
        for x in dic[a]:    # 상위노드와 연결된 하위노드 중에서
            if x not in visitedBfs:     # 방문 된적이 없다면
                queue.append(x)     # 작업열에 추가
                visitedBfs.append(x)    # 방문된 노드에 추가


dfs(v)
bfs(v)
print(*visitedDfs)
print(*visitedBfs)  # 리스트 형태가 아닌 노드의 번호만 출력해야 하므로 분해하여 출력