DFS와 BFS

❓문제

❗문제 정리

📑코드

from collections import deque

def bfs(graph, start, visited):
    queue=deque([start])#시작한 노드 큐에 넣고 방문하지 않은 인접한 노드들 넣기
    visited[start]=True#현재 위치한 노드 방문처리
    
    while queue:#큐가 비어있지 않는 동
        v=queue.popleft()#큐 최상단에서 꺼낸 노드가 시작 노드
        print(v,end=' ')#방문 노드 출력

        for i in graph[v]:#기준노드에서 연결된 노드 i 가져오기
            if not visited[i]:#인접 노드 중 아직 방문하지 않았다면
                queue.append(i)#큐에 넣고
                visited[i]=True#방문 처리

def dfs(graph, v, visited):#v가 시작위치
#스택에 넣는다고하지만 그냥 실행
    visited[v]=True#현재 위치한 노드 방문처리
    print(v,end=' ')#방문 노드 출력

    for i in graph[v]:
        if not visited[i]:#아직 방문하지 않았다면
            dfs(graph, i, visited)#거기서 dfs다시 실행하기

n, m, v=map(int, input().split())            
graph=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
      
for i in range(len(graph)):#정점 번호가 작은것을 먼저 방문
  graph[i].sort()

visited_dfs=[False]*(n+1)
dfs(graph, v, visited_dfs)
print()#출력형식

visited_bfs=[False]*(n+1)
bfs(graph, v, visited_bfs)

📝코드 설명

def bfs(graph, start, visited):
    queue=deque([start])#시작한 노드 큐에 넣고 방문하지 않은 인접한 노드들 넣기
    visited[start]=True#현재 위치한 노드 방문처리
    
    while queue:#큐가 비어있지 않는 동
        v=queue.popleft()#큐 최상단에서 꺼낸 노드가 시작 노드
        print(v,end=' ')#방문 노드 출력

        for i in graph[v]:#기준노드에서 연결된 노드 i 가져오기
            if not visited[i]:#인접 노드 중 아직 방문하지 않았다면
                queue.append(i)#큐에 넣고
                visited[i]=True#방문 처리

bfs 주석 참조

def dfs(graph, v, visited):#v가 시작위치
#스택에 넣는다고하지만 그냥 실행
    visited[v]=True#현재 위치한 노드 방문처리
    print(v,end=' ')#방문 노드 출력

    for i in graph[v]:
        if not visited[i]:#아직 방문하지 않았다면
            dfs(graph, i, visited)#거기서 dfs다시 실행하기

dfs 주석 참조

n, m, v=map(int, input().split())            
graph=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

필요한 인수 받기
n(int): 정점의 수
m(int) : 간서의 수
v(int) : 시작 정점의 번호
graph : 인덱스와 연결된 노드들 넣기
a(int), b(int) : 연결된 노드들
간선이 양방향이기에 서로의 인덱스에 자기 자신을 넣어줘야함.

for i in range(len(graph)):#정점 번호가 작은것을 먼저 방문
  graph[i].sort()

방문할 수 있는 정점이 여러개인 경우에 정점 번호가 작은 것을 먼저 방문하라는 지시에 따라, 정점 수가 작은순서대로 바꾸어주기 위해 sort사용.

visited_dfs=[False]*(n+1)
dfs(graph, v, visited_dfs)
print()#출력형식

visited_bfs=[False]*(n+1)
bfs(graph, v, visited_bfs)

dfs, bfs를 위한 방문처리확인 변수인 visited 만들어주고 출력형식을 맞추기 위해, print()사용.

🎖제출 결과

💡insight

출력형식이 잘못된 경우, print()를 써서 해결!
print()를 쓴 경우,

print("\n")를 쓴 경우,