BFS, DFS

• 인접 리스트 (그래프) 이용
• 데이터 구성(예시)

1: [2, 3]
2: [1, 4, 5]
3: [1, 4]
4: [2, 3]
5: [2]

정점 1~5, 간선: (1–3), (1–2), (2–5), (3–4), (2–4)
graph[i] = i와 인접한 정점 번호들의 리스트
graph[i][j] = i의 j번째 이웃 정점 번호

• 선언 & 입력

from collections import deque
import sys

# input = sys.stdin.readline
# n, m, start = map(int, input().split())

n, m, start = [int(x) for x in input().split()]

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)            # 무방향일 때

for i in range(1, n + 1):
    graph[i].sort()               # 방문 순서 고정(필요 시)

• 구현

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(start: int):
    visited = [False] * (n + 1)
    order = []

    def rec(u):
        visited[u] = True
        order.append(u)
        for w in graph[u]:
            if not visited[w]:
                rec(w)

    rec(start)
    return order

def bfs(start: int):
    visited = [False] * (n + 1)
    q = deque([start])
    visited[start] = True
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for w in graph[u]:
            if not visited[w]:
                visited[w] = True
                q.append(w)
    return order

print(*dfs(start))
print(*bfs(start))

전역변수 dfs ver

def dfs(node):
  """
  전역 변수 vis, asw를 사용하여 깊이 우선 탐색을 수행합니다.
  """
  global vis, asw # 함수 안에서 전역 변수를 수정할 것임을 명시

  vis[node] = True
  asw.append(node)
  
  for neighbor in graph[node]:
    if not vis[neighbor]:
      dfs(neighbor)

# --- 전역 변수 선언 및 초기화 (가장 직관적인 위치) ---
# 1. 탐색에 필요한 전역 변수를 준비합니다.
vis = [False] * (n + 1)
asw = []

# 2. 준비된 변수들을 사용하여 함수를 호출합니다.
dfs(v)

legacy

from collections import deque

n, m, v = [int(x) for x in input().split()]

graph = [[] for _ in range(n+1)]
for _ in range(m):
  a, b = [int(x) for x in input().split()]
  graph[a].append(b)
  graph[b].append(a)
for i in range(1,n+1):
  graph[i].sort()
  
def bfs(c):
  global vis
  asw = []
  q = deque()
  q.append(c)
  vis[c] = 1
  while q:
    c = q.popleft()
    asw.append(c)
    for a in graph[c]:
      if vis[a] == 0:
        q.append(a)
        vis[a] = 1
  return asw

def dfs(c):
  global vis, asw
  asw.append(c)
  vis[c] = 1
  for a in graph[c]:
    if vis[a]==0:
      dfs(a)
  return asw

vis = [0]*(n+1)
asw = []
print(*dfs(v))

vis = [0]*(n+1)
print(*bfs(v))

from collections import deque

# 'n', 'v', 'graph'는 이미 정의되어 있다고 가정합니다.
# 예시:
# n, m, v = map(int, input().split())
# graph = [[] for _ in range(n + 1)]
# for _ in range(m):
#     a, b = map(int, input().split())
#     graph[a].append(b)
#     graph[b].append(a)
# for i in range(1, n + 1):
#     graph[i].sort()

def dfs(start_node, n):
  """
  깊이 우선 탐색(DFS)을 수행하고 방문 순서를 반환합니다.
  """
  visited = [False] * (n + 1)
  result = []
  stack = [start_node]

  while stack:
    node = stack.pop()
    if not visited[node]:
      visited[node] = True
      result.append(node)
      # 스택의 특성을 살리기 위해 역순으로 추가
      stack.extend(sorted(graph[node], reverse=True))
  return result

def bfs(start_node, n):
  """
  너비 우선 탐색(BFS)을 수행하고 방문 순서를 반환합니다.
  """
  visited = [False] * (n + 1)
  result = []
  queue = deque([start_node])
  visited[start_node] = True

  while queue:
    node = queue.popleft()
    result.append(node)
    for neighbor in sorted(graph[node]):
      if not visited[neighbor]:
        visited[neighbor] = True
        queue.append(neighbor)
  return result

# 함수 호출
print(*dfs(v, n))
print(*bfs(v, n))

격자(map) 문제 (2D grid)

• 그래프를 따로 만들지 않고 좌표 + 방향 벡터로 탐색
  이웃: 상/하/좌/우(또는 대각 포함)

• 입력 예시 & 선언
  1) 공백으로 구분된 0/1

H W
1011
0100
1110

H, W = map(int, input().split())
grid = [list(map(int, input().strip())) for _ in range(H)]

• 구현 (BFS; 연결된 1 영역 탐색 예)

from collections import deque

dirs = [(1,0), (-1,0), (0,1), (0,-1)]

def bfs_grid(sr, sc):
    if grid[sr][sc] == 0:
        return []  # 시작이 벽/0이면 빈 영역
    visited = [[False]*W for _ in range(H)]
    q = deque([(sr, sc)]); visited[sr][sc] = True
    cells = []

    while q:
        r, c = q.popleft()
        cells.append((r, c))
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and not visited[nr][nc] and grid[nr][nc] == 1:
                visited[nr][nc] = True
                q.append((nr, nc))
    return cells

# 사용 예: (0,0)에서 시작하는 1-영역 좌표들
component = bfs_grid(0, 0)
# print(component)