[백준] 1260. DFS와 BFS

 

📌문제

https://www.acmicpc.net/problem/1260

 

🎖️난이도

 

✔️풀이

# sol1) 인접 행렬 & 재귀(dfs) & 큐(bfs)
from collections import deque
import sys

sys.setrecursionlimit(1000000) # 파이썬 기본 재귀 깊이 제한 늘리기 (런타임 에러 방지)


n, m, v = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 노드
graph = [[0] * (n+1) for _ in range(n+1)] # 인접 행렬로 그래프 저장 (0으로 초기화)
visited_dfs = [False] * (n+1) # list에서 append 후 in으로 체크하는 것보다 빠름
visited_bfs = [False] * (n+1)

# 그래프 입력받기 (인접 행렬)
for _ in range(m):
    start, end = map(int, input().split())
    graph[start][end] = 1
    graph[end][start] = 1
    

# dfs, bfs 함수 정의 - 여기서 print
def dfs(v):
    print(v, end = " ")         # 방문 시작 노드 출력 먼저! (재귀 & 앞부터 출력하기 위함)
    for i in range(1, n+1):     # 숫자 작은 것부터 탐색
        # i가 v와 연결된 노드고, 이전에 방문한 적은 없었다면 => True로 바꾸고 시작노드로 ㄱㄱ
        if graph[v][i] == 1 and visited_dfs[i] == False: 
            visited_dfs[i] = True
            dfs(i) # 2->4->3
                
def bfs(v):
    q = deque()
    q.append(v) 
    
    # 큐가 빌 때까지 반복
    while q:
        n = q.popleft() # FIFO
        if visited_bfs[n] == False:    # 이전에 방문한 적이 없다면
            visited_bfs[n] = True      # True로 바꾸고 바로 방문
            print(n, end = " ")        # 방문 시작 노드 출력 
            for i in range(1, n+1):    # 숫자 작은 것부터 탐색
                # i가 v와 연결된 노드고, 이전에 방문한 적은 없었다면 => 큐에 차례대로 추가
                if graph[n][i] == 1 and visited_bfs[i] == False:
                    q.append(i)
            

visited_dfs[v] = True # 탐색 시작 노드 방문
dfs(v)
print()
bfs(v)

 

# sol2) 인접 리스트 & 스택(dfs) & 큐(bfs)

from collections import deque


n, m, v = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 노드
graph = {i:[] for i in range(1, n+1)} # 인접 행렬로 그래프 저장
#visited_dfs = [] # list로 정의 후 append, in 이용 시 O(N)
#visited_bfs = []

# 그래프 입력받기 (인접 리스트)
for _ in range(m+1):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)
    
for key in graph:
    graph[key].sort() # 오름차순 정렬
    

# dfs, bfs 정의 - dict로 return
def dfs(graph, v):
    visited = {} # list에 비해 시간 단축 (dict)
    stack = [v]
    
    while stack:
        n = stack.pop()
        if n not in visited: # O(1)
            visited.setdefault(n)
            stack += reversed(graph[n])
    return visited

def bfs(graph, v):
    visited = {}
    queue = deque([v])
    
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.setdefault(n)
            queue += graph[n]
    return visited

print(' '.join(list(map(str,dfs(graph, v)))))
print(' '.join(list(map(str,bfs(graph, v)))))

 

---

그래프 입력 받기 (그래프 구현 방식 2가지)

1. 인접 행렬

2차원 배열으로 표현하는 방식

graph = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 0],
    [0, 1, 0, 0]
]

2. 인접 리스트

연결 리스트로 표현하는 방식

• 2차원 list로 저장

graph = [
    [],
    [2, 3, 8], # 1번 노드
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

• dictionary로 저장

graph = {
    'A' : ['B'],
    'B' : ['A', 'C', 'H'],
    ...
    }