[코딩테스트] BFS, DFS

이 포스팅의 목표는, 코딩테스트에서 자주 사용되는 핵심 문법들을 템플릿 형태로 정리하고, 이를 빠르게 외워서 실전 문제에 바로 적용할 수 있도록 만드는 것이다.

---

✏️ BFS

■ 핵심 개념

• 시작 노드에서 출발하여 인접한 노드를 너비 우선으로 탐색.
• 큐(Queue)를 이용하여 구현.
• 방문 여부를 체크하는 visited 리스트가 필수 (중복 방문 방지).

■ 한줄 요약

1. 큐에 시작 노드 삽입
2. 큐에서 꺼낸 후 인접 노드 탐색
3. 방문 안했으면 큐에 추가 및 방문 처리

■ 구현

1. 인접 리스트 방식

• 그래프를 딕셔너리로 표현
• 노드마다 연결된 노드의 리스트를 가짐

인수: 시작 노드, 그래프, visited 배열

from collections import deque

def BFS(start, graph, visited):
	queue = deque([start])
	visited[start] = True

	while queue:
		current = queue.popleft()
		
		for next in graph[current]:
			if not visited[next]:
				visited[next] = True
				queue.append(next)

2. 인접 행렬 방식

• 인접 행렬로 그래프를 표현
• 노드 수가 적고 간선이 많은 경우 유리

인수: 시작 노드, 그래프, visited 배열

from collections import deque

def BFS(start, graph, visited):
	queue = deque([start])
	visited[start] = True

	while queue:
		current = queue.popleft()
		
		for next in range(len(graph)):
			if graph[current][next] == 1 and not visited[next]:
				visited[next] = True
				queue.append(next)

3. 격자 기반 방식

• 미로 탐색, 최단거리 구하기 등에 자주 등장
• 2차원 배열로 그래프 표현

인수: 시작 x좌표, y좌표

from collections import deque

dy = [-1, 1, 0, 0] #상, 하
dx = [0, 0, -1, 1] #좌, 우

def BFS(x, y):
	queue = deque()
	queue.append((x, y))
	visited[y][x] = True

	while queue:
		x, y = queue.popleft()

		for dir in range(4):
			nx = x + dx[dir]
			ny = y + dy[dir]

			if 0 <= nx < M and 0 <= ny < N:
				if not visited[ny][nx] and graph[ny][nx] == 1:
					visited[ny][nx] = True
					queue.append((nx, ny))

---

✏️ DFS

■ 핵심 개념

• 시작 노드에서 출발하여 자식 노드를 하나씩 깊이 탐색.
• 재귀 또는 스택을 이용해 구현.
• 방문 여부를 체크하는 visited 리스트가 필수 (무한루프 방지).

■ 한줄 요약

1. 방문 처리
2. 인접 노드 순회
3. 방문 안했으면 DFS 재귀 호출

■ 구현

1. 인접 리스트 방식

• 그래프를 딕셔너리로 표현
• 노드마다 연결된 노드의 리스트를 가짐

인수: 현재 노드, 그래프, visited 배열

def DFS(current, graph, visited):
	visited[current] = True
    
    for next in graph[current]:
    	if(visitied[next] == False):
        	DFS(next, graph, visited)

2. 인접 행렬 방식

• 인접 행렬로 그래프를 표현
• 노드 수가 적고 간선이 많은 경우 유리

인수: 현재 노드, 그래프, visited 배열

def DFS(current, graph, visited):
	visited[current] = True
    
    for next in range(len(graph)):
    	if(graph[current][next] == 1 and visited[next] == False):
        	DFS(next, graph, visited)

3. 격자 기반 방식

• 미로 탈출, 좌표 기반 이동에서 사용
• 2차원 배열로 그래프를 표현

인수: 현재 x좌표, 현재 y좌표

dy = [-1, 1, 0, 0] #상, 하
dx = [0, 0, -1, 1] #좌, 우

def DFS(x, y):
	visited[y][x] = True
    
    for dir in range(4):
    	nx = x + dx[dir]
        ny = y + dy[dir]
        
        if((0 <= nx < M) and (0 <= ny < N)):
        	if(visited[ny][nx] == False and graph[ny][nx] == 1):
            	DFS(nx, ny)