[백준] 1260. DFS와 BFS (Python)

백준 문제 풀이 - 그래프 탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

4 5 1
1 2
1 3
1 4
2 4
3 4

>> 1 2 4 3
>> 1 2 3 4

5 5 3
5 4
5 2
1 2
3 4
3 1

>> 3 1 2 5 4
>> 3 1 4 2 5

1000 1 1000
999 1000

>> 1000 999
>> 1000 999

💬 풀이

🎵 첫번째 풀이

from collections import deque


N, M, V = map(int, input().split())		# 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호
maps = [[] for _ in range(N+1)]			# 인접리스트

for _ in range(M):
    i, j = map(int, input().split())
    maps[i].append(j)
    maps[j].append(i)

for m in maps:
    m.sort()


def dfs(n):

    visitedDFS[n] = True
    print(n, end = " ")

    for i in maps[n]:
        if not visitedDFS[i]:
            dfs(i)

def bfs(n):

    visitedBFS = [False] * (N+1)

    queue = deque()

    queue.append(n)
    visitedBFS[n] = True

    while queue:

        now = queue.popleft()
        print(now, end = " ")

        for i in maps[now]:
            if not visitedBFS[i]:
                queue.append(i)
                visitedBFS[i] = True


visitedDFS = [False] * (N+1)
dfs(V)
print()
bfs(V)

✒️ 생각