[백준/파이썬] 1260번 DFS와 BFS 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1260번 DFS와 BFS
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

무방향 그래프와 시작 정점 V가 주어질 때 DFS 방문 순서와 BFS 방문 순서를 출력하는 문제입니다.

인접 정점이 여러 개면 번호가 작은 정점부터 방문합니다.

코드

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

l = []
for _ in range(m):
    l.append(tuple(map(int, input().split())))

def dfs(n, m, v, l):
    result = [v]
    stack = [v]
    check = dict()
    for i in range(1, n+1):
        check[i] = False
    check[v] = True

    while len(stack) > 0:
        tmp = []
        for line in l:
            if line[0] == stack[-1] and not check[line[1]]:
                tmp.append(line[1])
            elif line[1] == stack[-1] and not check[line[0]]:
                tmp.append(line[0])
        if len(tmp) == 0:
            stack.pop()
        else:
            point = min(tmp)
            stack.append(point)
            result.append(point)
            check[point] = True
    return result

def bfs(n, m, v, l):
    result = [v]
    queue = [v]
    check = dict()
    for i in range(1, n+1):
        check[i] = False
    check[v] = True

    while len(queue) > 0:
        tmp = []
        for line in l:
            if line[0] == queue[0] and not check[line[1]]:
                tmp.append(line[1])
            elif line[1] == queue[0] and not check[line[0]]:
                tmp.append(line[0])
        if len(tmp) == 0:
            queue.pop(0)
        else:
            point = min(tmp)
            queue.append(point)
            result.append(point)
            check[point] = True
    return result

print(*dfs(n, m, v, l))
print(*bfs(n, m, v, l))

설명

간선 목록에서 현재 정점과 연결된 미방문 정점을 모아 가장 작은 번호(min)를 선택해 진행합니다.

• DFS: 스택 기반 깊이 우선 탐색
• BFS: 큐 기반 너비 우선 탐색

각 탐색의 방문 순서를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---