스파르탄 365 3주차 (1) DFS와 BFS

3주차

백준 1260번 DFS와 BFS

문제링크 : https://www.acmicpc.net/problem/1260

💡 풀이 전 계획과 생각

https://velog.io/@dawnofspring/DFS-BFS 에 정리했던 내용 그대로 이용

💡 풀이

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())
# velog: 1-N개 해야하니까 N+1개 생
graph = [list() for _ in range(N+1)]

# velog: 재귀함수로 간단하게
def dfs(v):
    print(v, end=' ')
    visited[v] = True
    # 모든 정점을 방문하는 반복문
    for node in graph[v]:
        if not(visited[node]):
            dfs(node)

# velog: bfs는 꼭 큐를 이용해야한다. 반드시 큐가 필요해서 덱을 임포
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            print(v, end=' ')
            for node in graph[v]:
                q.append(node)

for _ in range(M):
    fir_node, sec_node = map(int, sys.stdin.readline().split())
    # velog
    graph[fir_node].append(sec_node)
    graph[sec_node].append(fir_node)

# velog: 가장 낮은 번호부터 방문하기 위한 정
for g in graph:
    g.sort()

# velog
visited = [False] * (N+1)
dfs(V)
print()
visited = [False] * (N+1)
bfs(V)

🧐 막혔던 점과 고민

• 주어진 인풋으로 인접 리스트(그래프)를 어떻게 만드는가 ?

👏🏻 알게된 개념과 소감

• 주어진 인풋으로 인접 리스트(그래프)를 어떻게 만드는 법

💡 개선 방향

• dfs 함수를 재귀함수 구현에서 스택을 사용한 부분으로 구현하고 싶다.