정보처리기사 DFS 완전 정복 — 스택 안 그리고 백트래킹 푸는 법

스택 그리다가 시간 다 보내는 그 문제

정보처리기사 필기 자료구조 파트에서 단골로 출제되는 주제가 바로 그래프 운행법, 그중에서도 깊이 우선 탐색(DFS, Depth-First Search)입니다. 많은 수험생이 DFS 문제를 만나면 스택(Stack)을 일일이 네모 칸으로 그려가며 풀다가 시간을 허비하거나, 백트래킹 과정에서 방문 순서를 놓쳐 답을 틀립니다. 이 강의는 그 부담을 덜어주는 실전형 풀이법에 집중합니다.

DFS는 원리만 손에 익으면 어떤 트리·그래프 예제가 나와도 빠르게 방문 순서를 적어낼 수 있는 영역입니다. 한 번 제대로 잡아두면 시험에서 확실한 득점원이 됩니다.

DFS란 무엇인가 — 원리부터 정확히

깊이 우선 탐색은 이름 그대로 한 방향으로 갈 수 있는 데까지 최대한 깊이 들어간 뒤, 더 갈 곳이 없으면 바로 직전 갈림길로 되돌아가(백트래킹) 다른 방향을 시도하는 탐색 방법입니다. 구현 방식은 두 가지가 있는데, 결과는 동일합니다.

• 재귀 호출 방식 — 함수가 자기 자신을 다시 호출하며, 시스템이 자동으로 만드는 콜 스택(call stack)이 우리가 손으로 그리던 스택 역할을 대신합니다.
• 명시적 스택 자료구조 방식 — 배열이나 스택 변수를 직접 만들어 push/pop으로 다음 방문 노드를 관리합니다.

정보처리기사 시험에서는 대부분 재귀 방식의 동작 원리를 이해하고 방문 순서를 손으로 추적하는 문제가 나오므로, 이 강의와 이 글에서도 재귀 방식을 기준으로 설명합니다. 핵심 규칙은 딱 두 가지입니다.

1. 노드에 도착하면 즉시 "방문 완료" 표시를 한다. (다시 방문하지 않도록)
2. 현재 노드의 이웃 중 아직 방문하지 않은 노드가 있으면 그중 하나로 더 깊이 들어가고, 없으면 바로 직전 노드로 되돌아간다.

이 두 규칙만 기계적으로 반복하면 스택을 그리지 않고도 방문 순서를 끝까지 추적할 수 있습니다.

BFS와 헷갈리지 않게 비교하기

DFS와 항상 짝을 지어 출제되는 개념이 너비 우선 탐색(BFS, Breadth-First Search)입니다. 둘의 차이는 "다음에 어디를 방문하느냐"에 대한 전략 차이입니다.

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
사용 자료구조	스택(재귀 호출 스택 포함)	큐(Queue)
진행 방식	한 갈래로 끝까지 파고든 뒤 되돌아옴	가까운 노드부터 한 단계씩 넓게 퍼짐
대표 활용	백트래킹, 경로 존재 여부 판단, 위상 정렬	최단 경로(가중치 없는 그래프), 레벨별 탐색
기억법	"깊게 먼저" — 갈 수 있는 데까지 간다	"넓게 먼저" — 가까운 곳부터 훑는다

시험에서는 같은 그래프를 주고 "DFS 방문 순서는?"과 "BFS 방문 순서는?"을 나란히 묻는 경우가 많으므로, 두 방법의 결과가 서로 다르게 나온다는 감각을 반드시 익혀야 합니다.

예제 그래프로 방문 순서 직접 추적하기

말로만 설명하면 감이 안 잡히니, 실제 예제 그래프로 스택을 그리지 않고 방문 순서를 암산으로 추적해 보겠습니다. 아래와 같은 무방향 그래프가 있다고 가정합니다.

간선 목록: 1-2, 1-3, 2-4, 3-4, 4-5

이를 인접 리스트로 정리하면 다음과 같습니다. (탐색 규칙: 이웃 노드는 항상 번호가 작은 순서부터 방문합니다. 이 규칙 자체가 시험 문제에서 자주 강조되는 조건입니다.)

노드	인접 노드(오름차순)
1	2, 3
2	1, 4
3	1, 4
4	2, 3, 5
5	4

스택을 그리는 대신, "현재 위치"와 "지금까지 지나온 한 줄짜리 경로 메모"만 머릿속(또는 종이 한 줄)에 유지하면서 두 규칙을 반복합니다. 아래 표가 그 과정입니다.

단계	경로 메모	현재 노드	이웃 확인	판단
1	1	1	2, 3 모두 미방문	가장 작은 2로 이동 → 1 방문
2	1 → 2	2	1(방문됨), 4(미방문)	4로 이동 → 2 방문
3	1 → 2 → 4	4	2(방문됨), 3·5(미방문)	가장 작은 3으로 이동 → 4 방문
4	1 → 2 → 4 → 3	3	1(방문됨), 4(방문됨)	더 갈 곳 없음 → 3 방문 후 4로 복귀
5	1 → 2 → 4	4	남은 이웃 5(미방문)	5로 이동
6	1 → 2 → 4 → 5	5	4(방문됨)	더 갈 곳 없음 → 5 방문 후 4로 복귀
7	1 → 2 → 4	4	이웃 전부 확인됨	2로 복귀
8	1 → 2	2	이웃 전부 확인됨	1로 복귀
9	1	1	3은 이미 방문됨	더 갈 곳 없음 → 탐색 종료

"경로 메모"는 화살표로 이어진 한 줄일 뿐, 상자를 겹겹이 쌓는 스택 그림이 아닙니다. 이 한 줄이 늘어나면 "더 들어간다", 줄어들면 "되돌아간다(백트래킹)"는 뜻입니다.

이 과정을 통해 얻은 최종 방문 순서는 1 → 2 → 4 → 3 → 5입니다. 노드가 5개인 그래프에서 5개 노드가 정확히 한 번씩만 등장했는지 세어보면 검산이 끝납니다 (1, 2, 3, 4, 5 — 총 5개, 중복 없음 확인).

재귀 DFS 코드로 검증하기

손으로 추적한 결과가 맞는지, 위 그래프를 그대로 코드로 옮겨 재귀 DFS를 돌려보면 검증할 수 있습니다.

const graph = {
  1: [2, 3],
  2: [1, 4],
  3: [1, 4],
  4: [2, 3, 5],
  5: [4],
};

const visited = new Set();
const order = [];

function dfs(node) {
  visited.add(node);   // 규칙 1: 도착 즉시 방문 표시
  order.push(node);

  for (const next of graph[node]) {
    if (!visited.has(next)) {
      dfs(next);        // 규칙 2: 미방문 이웃으로 더 깊이 진입
    }
  }
  // for문이 끝나면 함수가 종료되며 자동으로 이전 노드로 복귀(백트래킹)
}

dfs(1);
console.log(order); // [1, 2, 4, 3, 5]

손으로 추적한 1 → 2 → 4 → 3 → 5와 코드 실행 결과가 정확히 일치합니다. 재귀 함수가 자기 자신을 호출할 때마다 시스템이 알아서 콜 스택에 "돌아올 자리"를 쌓아두기 때문에, 우리가 직접 스택을 그리지 않아도 dfs(next) 호출이 끝나는 순간 자동으로 이전 노드로 돌아가는 것입니다.

백트래킹과 DFS의 관계

정보처리기사 강의 제목에 왜 "백트래킹"이 함께 붙어 있는지 궁금할 수 있습니다. 이유는 간단합니다. 백트래킹(Backtracking)은 DFS 방식으로 가능한 경우의 수를 파고들다가, 조건에 맞지 않으면 그 선택을 취소하고 이전 상태로 되돌아가는 탐색 기법이기 때문입니다. 즉 DFS는 백트래킹이 동작하는 기본 골격이고, 백트래킹은 그 골격 위에 "선택 → 확인 → 취소"라는 로직을 얹은 응용이라고 볼 수 있습니다.

대표적인 백트래킹 예제인 순열(permutation) 생성으로 이 관계를 확인해 보겠습니다.

function permute(arr, path = [], used = []) {
  if (path.length === arr.length) {
    console.log(path.join(''));  // 순열 하나 완성
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    if (used[i]) continue;       // 이미 선택한 숫자는 건너뛴다

    used[i] = true;
    path.push(arr[i]);           // 선택

    permute(arr, path, used);    // DFS처럼 더 깊이 파고들기

    path.pop();                  // 백트래킹: 선택을 취소
    used[i] = false;             // 되돌리고 다음 후보 시도
  }
}

permute([1, 2, 3]);
// 123, 132, 213, 231, 312, 321

그래프를 방문하던 dfs()와 구조가 똑같습니다. "더 깊이 들어가기"는 permute()의 재귀 호출이, "되돌아가기"는 path.pop()과 used[i] = false가 맡고 있을 뿐입니다. 이 유사성을 이해하면 그래프 DFS 문제뿐 아니라 완전 탐색·조합·순열 문제까지 같은 사고방식으로 풀 수 있습니다.

시험에서 자주 나오는 함정

• 이웃 노드 방문 순서 규칙을 놓친다 — 문제에서 "번호가 작은 순서로", "알파벳 순서로" 등 방문 규칙을 명시하는데 이를 무시하고 아무 순서로나 방문 순서를 적어 오답 처리되는 경우가 많습니다. 규칙을 반드시 먼저 확인하세요.
• 방문 표시 시점을 헷갈린다 — "노드에 도착했을 때" 방문 표시를 하는지, "이웃을 확인할 때" 미리 표시하는지가 문제마다 조금씩 다르게 서술될 수 있습니다. 이 글의 기준은 도착 즉시 표시이며, 대부분의 정보처리기사 기출도 이 방식을 따릅니다.
• 백트래킹으로 어디로 되돌아가는지 헷갈린다 — 항상 "가장 최근에 거쳐온 노드"로 되돌아갑니다. 임의의 이전 노드가 아니라 직전 경로의 마지막 지점이라는 점을 기억하세요.
• 무방향 그래프에서 왔던 길을 다시 세는 실수 — 예를 들어 2에서 4로 갔다가 4에서 다시 2로 되돌아가는 간선을 "새로운 방문"으로 착각하면 안 됩니다. 이미 방문한 노드는 재방문하지 않습니다.
• DFS와 BFS 결과를 뒤섞어 적는다 — 같은 그래프라도 DFS와 BFS의 방문 순서는 대부분 다릅니다. 문제가 어떤 탐색을 요구하는지 문두를 다시 확인하는 습관이 필요합니다.

이런 분께 추천합니다

• 정보처리기사 필기를 준비하는데 그래프 운행법·DFS만 유독 헷갈리는 수험생
• 스택을 그리며 풀다 보니 시간이 부족하거나 자꾸 실수하는 분
• 비전공자라 자료구조 개념이 낯선 분
• 코딩 테스트·알고리즘 학습을 위해 DFS와 백트래킹 원리를 잡아두려는 분

수강 정보

항목	내용
수강료	무료
분류	자격증
강사	누구나패스
구성	핵심 단일 강의 (실전 풀이 완성형)
학습 방식	온라인 영상 — 원하는 시간에 반복 수강

무료로 제공되는 강의이니 부담 없이 들어보고, 시험 직전 복습용으로도 활용해 보세요.

자주 묻는 질문 (FAQ)

Q. 자료구조를 전혀 모르는데 따라갈 수 있나요?

네. 그래프와 스택 개념이 낯설다는 전제에서 출발해 직관적으로 설명하므로 비전공자도 충분히 이해할 수 있습니다.

Q. 스택을 꼭 그려야 하나요?

이 강의의 핵심이 바로 그것입니다. 스택을 일일이 그리지 않고도 "현재 위치 + 경로 메모" 한 줄만으로 방문 순서를 따라가는 방법을 알려드려 풀이 시간을 크게 줄여줍니다.

Q. 이웃 노드는 항상 번호가 작은 순서로 방문하나요?

많은 기출 문제가 오름차순 방문을 기본 규칙으로 제시하지만, 문제에 따라 다른 규칙(주어진 인접 리스트 순서 그대로 등)을 명시하기도 합니다. 이 글과 강의의 예제는 오름차순 규칙을 기준으로 하되, 실제 시험에서는 문제 지문의 규칙을 최우선으로 따라야 한다는 점을 반드시 함께 강조합니다.

Q. BFS도 함께 다루나요?

강의는 DFS 실전 풀이에 집중하되, BFS(너비 우선 탐색)와의 차이점을 비교해 두 개념을 헷갈리지 않도록 정리해 드립니다.

Q. 수강료가 정말 무료인가요?

네, 별도 결제 없이 무료로 수강할 수 있습니다.

지금 바로 시작하세요

스택 그림 없이 DFS를 빠르게 푸는 법, 더 미루지 말고 지금 익혀두세요. 시험장에서 만나는 한 문제가 합격과 불합격을 가를 수 있습니다.

강의 자세히 보기 →