백준 1260 DFS와 BFS Python

Derhon·2023년 11월 18일
0
post-thumbnail

백준 1260 DFS와 BFS

나의 답

from collections import deque
import sys

N, M, V = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [[False] * (N + 1) for _ in range(N + 1)] #0번 인덱스는 제외하고 연결된 노드 그래프

dfs_visited = [False] * (N + 1)
bfs_visited = [False] * (N + 1)

for i in range(M): #그래프에서 연결된 부분들 True로 초기화
    node1, node2 = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[node1][node2] = True
    graph[node2][node1] = True
def dfs(node):
    dfs_visited[node] = True #해당 노드 방문 완료
    print(node, end=' ')
    for i in range(1, N + 1): #그래프에서 해당 노드와 연결된 부분 순회
        if not dfs_visited[i] and graph[node][i]: #특정 노드와 연결 되어있으면서, 그 노드를 방문하지 않ㅇ느 경우
            dfs(i)

def bfs(node):
    q = deque([node]) #큐에서 시작 노드는 이미 방문 완료
    bfs_visited[node] = True
    while q:
        node = q.popleft() #먼저 방문해야하는 노드를 빼줌
        print(node, end=' ')
        for i in range(1, N + 1):
            if not bfs_visited[i] and graph[node][i]: #방문한 노드와 연결된 노드 중, 아직 방문하지 않은 노드는 큐에 담고 방문처리함
                q.append(i)
                bfs_visited[i] = True

dfs(V)
print()
bfs(V)

생각

DFS와 BFS의 기초를 학습하기에 좋은 문제였다.
기초도없는 나이기에 문제를 두 번 풀어봤다.
참고

profile
🧑‍🚀 이사했어요 ⮕ https://99uulog.tistory.com/

0개의 댓글