그래프 표현 방식과 백트래킹 가지치기

단순 DFS와 백트래킹이 갈라지는 지점

백트래킹을 'DFS인데 되돌아가는 것'으로만 알면 문제 앞에서 구분이 안 된다. 인접 행렬과 인접 리스트 선택 기준, DFS와 BFS를 나누는 축, 그리고 가지치기 조건.

게시 2026/03/13

By GoldBoll

7 분읽는 시간

그래프 표현 방식과 백트래킹 가지치기

백트래킹을 “DFS인데 되돌아가는 것”이라고만 알고 있으면 문제 앞에서 둘을 구분하지 못한다. 이 글에서는 그래프 탐색의 기반부터 다시 쌓아 그 차이를 짚으려 한다 — 인접 행렬과 인접 리스트 중 무엇을 고를지, DFS와 BFS를 무엇으로 나눌지, 그리고 백트래킹이 단순 DFS와 갈라지는 지점인 가지치기 조건이다.

그래프 — 표현 방식과 DFS·BFS 선택 기준

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조다. 방향 그래프인지 무방향 그래프인지, 간선에 가중치(비용·거리 값)가 붙는지, 사이클이 존재하는지에 따라 문제 풀이 접근이 달라진다. 강의를 들으면서 이 세 가지(방향성·가중치·순환 여부)를 문제를 읽을 때 먼저 확인하는 체크 항목으로 삼기로 했다.

구현에서 제일 먼저 결정할 것은 그래프를 어떻게 표현하느냐다. 인접 행렬과 인접 리스트를 비교해 보면:

표현	장점	단점
인접 행렬	간선 존재 확인이 빠름 O(1)	메모리 O(V^2)로 큼
인접 리스트	메모리 효율 좋음 O(V+E)	간선 존재 확인은 느릴 수 있음
추천 상황	정점 수 작고 밀집 그래프	희소 그래프/일반 코테

일반적인 코딩테스트는 간선이 드문 희소 그래프가 많아서 인접 리스트가 기본이 된다. 문제에서 그래프를 보면 먼저 표현 방식을 결정하는 것이 구현 난이도를 크게 좌우한다는 걸 느꼈다.

탐색은 DFS(깊이 우선, 재귀 또는 스택)와 BFS(가까운 레벨부터, 큐)로 나뉜다. 템플릿으로 외워둘 코드는 이 정도다.

  
// DFS (재귀)
void dfs(int u){
  visited[u] = true;
  for(int v : graph[u]) if(!visited[v]) dfs(v);
}

// BFS
queue<int> q; q.push(start); visited[start]=true;
while(!q.empty()){
  int u=q.front(); q.pop();
  for(int v: graph[u]) if(!visited[v]){ visited[v]=true; q.push(v);} 
}

알고리즘	복잡도	비고
DFS	O(V + E)	인접 리스트 기준
BFS	O(V + E)	최단 거리(무가중치) 문제에 자주 사용
인접 행렬 탐색	O(V^2)	정점이 많을수록 비효율 가능

직접 정리하면서 확인한 건, DFS와 BFS 중 무엇을 고르느냐보다 방문 처리와 중복 방문 방지를 정확히 하는 게 더 자주 틀리는 지점이라는 것이다. 큐에 넣는 시점에 방문 표시를 하는 것처럼, 방문 처리 위치를 틀리면 같은 정점을 여러 번 밟게 된다.

다음에 할 것:

인접 리스트 템플릿으로 DFS/BFS 기본 문제 1개씩 풀이
인접 행렬/리스트 변환 연습으로 표현 방식 전환 감각 익히기

백트래킹 — 가지치기가 만드는 차이

백트래킹은 완전탐색 중 유망하지 않은 분기를 조기에 제거(pruning, 가지치기)해 탐색량을 줄이는 기법이다. 상태공간트리에서 부분 해답을 확장하다가 조건을 위반하면 즉시 되돌아온다(backtrack). 이때 현재 경로가 해답으로 이어질 가능성을 판정하는 것이 유망 함수(promising function)다. 대표 문제로는 N-Queen, 부분집합 합, 스도쿠, 그래프 색칠(CSP)이 있다.

동작 구조는 템플릿 하나로 정리된다.

  
void dfs(State cur){
  if (종료조건) { 정답 처리; return; }
  for (후보 c : 후보집합){
    if (!promising(cur, c)) continue; // 가지치기
    선택 적용
    dfs(다음 상태);
    선택 복구; // backtrack
  }
}

시간복잡도는 최악에는 여전히 지수적일 수 있다. 다만 유망 함수 품질이 좋을수록 체감 성능이 크게 개선된다. 결국 탐색 자체보다 “언제 버릴지”를 빠르게 결정하는 데 성능이 달려 있다.

강의를 듣기 전에는 백트래킹을 그냥 DFS의 변형 정도로 생각했는데, 정리하고 나니 “제약 기반 탐색 최적화”로 이해하는 쪽이 맞았다. 후보를 어떻게 생성할지보다 가지치기 조건을 먼저 설계해야 성능이 올라간다.

다음에 할 것:

부분집합 합 문제를 pruning 유/무 2버전으로 구현해 실행 횟수 비교
N-Queen 충돌 판정(열/대각선)을 함수로 분리해 템플릿화

핵심 요약 — 그래프 문제는 표현 방식(인접 행렬 O(V²) vs 인접 리스트 O(V+E)) 결정이 구현 난이도를 좌우하고, 탐색에서는 방문 처리 위치가 가장 자주 틀리는 지점이다. 백트래킹은 후보 생성보다 가지치기 조건을 먼저 설계해야 성능이 나온다.

알고리즘

daily til

그래프 — 표현 방식과 DFS·BFS 선택 기준

백트래킹 — 가지치기가 만드는 차이

인기 태그