BOJ 풀이 노트: DFS 경로 탐색과 투 포인터 감각 복습

2026. 3. 20. · tech

오늘은 BOJ 13023과 3273을 묶어, 방문 처리 백트래킹이 핵심인 DFS와 중복 없이 쌍을 세는 투 포인터 구현 포인트를 실수 방지 중심으로 정리했다.

오늘은 그래프 탐색 1문제 + 정렬/투 포인터 1문제로 조합했다.

• BOJ 13023 - ABCDE
• BOJ 3273 - 두 수의 합

하나는 “깊이 조건을 만족하는 경로 존재 여부”를 묻는 문제고, 다른 하나는 “합이 특정 값이 되는 쌍의 개수”를 세는 문제라 사고 방식이 확실히 다르다. 하루 2문제 루틴에서 기본기 점검용으로 균형이 좋았다.

1) BOJ 13023 - ABCDE

문제 핵심 요약

사람 관계 그래프(무방향)에서 서로 다른 5명 A-B-C-D-E가 연속 친구 관계를 이루는 경로가 존재하는지 판단하는 문제다. 존재하면 1, 아니면 0을 출력한다.

접근 아이디어(왜 이 방법인지)

요구사항은 최단거리/개수 계산이 아니라 길이 4(정점 5개) 단순 경로 존재 여부다. 그래서 각 정점을 시작점으로 DFS를 돌리면서 깊이가 5가 되는 순간 즉시 성공 처리하면 된다.

핵심은 방문 배열을 재귀 진입/복귀 시점에 정확히 되돌리는 백트래킹이다.

• 진입: visited[nxt] = true
• 복귀: visited[nxt] = false

이 패턴이 깨지면 다른 분기 탐색이 막혀 오답이 난다.

시간/공간 복잡도

• 시간: 최악 O(N * (N + M)) 수준(시작점마다 DFS)
• 공간: O(N + M) (그래프 + 방문 배열 + 재귀 스택)

실수하기 쉬운 포인트

• 깊이 기준을 간선 수로 볼지 정점 수로 볼지 혼동하는 실수
  • 이번 구현은 시작 정점을 깊이 1로 두고 depth == 5면 성공
• 방문 해제를 안 해서 탐색 공간을 잘못 줄여버리는 실수
• 성공을 찾았는데도 끝까지 탐색해서 시간 낭비하는 실수

C++ 코드 설명(핵심 라인)

if (depth == 5) {
    found = true;
    return;
}

정점 5개 연속 경로를 찾는 즉시 종료 플래그를 세운다.

visited[nxt] = true;
dfs(nxt, depth + 1);
visited[nxt] = false;

백트래킹의 핵심. 분기 탐색 독립성을 보장한다.

다른 풀이 가능성

• 비트마스크 DFS로 방문 상태를 관리할 수도 있지만, 이 문제 크기에서는 일반 방문 배열 + 백트래킹이 가장 직관적이다.
• BFS는 “깊이 4 경로 존재” 자체는 볼 수 있어도 단순 경로 제약 처리 측면에서 DFS가 더 깔끔하다.

2) BOJ 3273 - 두 수의 합

문제 핵심 요약

서로 다른 두 수를 골라 합이 x가 되는 쌍의 개수를 구하는 문제다.

접근 아이디어(왜 이 방법인지)

정렬 후 양끝 포인터를 두면 한 번의 선형 스캔으로 해결된다.

• 합이 작으면 left++ (더 큰 값 필요)
• 합이 크면 right-- (더 작은 값 필요)
• 합이 같으면 정답 +1 후 양쪽 모두 이동

정렬 덕분에 포인터 이동 방향의 근거가 명확해서 O(N^2) 완전탐색을 O(N log N)으로 줄일 수 있다.

시간/공간 복잡도

• 시간: O(N log N) (정렬) + O(N) (투 포인터)
• 공간: O(1) 추가 공간(입력 배열 제외)

실수하기 쉬운 포인트

• 같은 인덱스를 두 번 쓰는 실수 (left < right 조건 필수)
• 합을 찾았을 때 한쪽 포인터만 움직여 무한 루프/중복 카운트가 나는 실수
• 입력 크기 대비 자료형을 불필요하게 크게/작게 잡는 실수

C++ 코드 설명(핵심 라인)

while (left < right) {
    int sum = a[left] + a[right];

반드시 서로 다른 두 원소만 보도록 루프 조건을 건다.

if (sum == x) {
    answer++;
    left++;
    right--;
}

정답을 찾았을 때 양쪽을 함께 이동해 같은 쌍을 다시 세지 않도록 한다.

다른 풀이 가능성

• 해시셋으로 x - a[i] 존재 여부를 확인하는 방식도 가능하다.
• 다만 정렬 + 투 포인터는 메모리 부담이 적고 구현 버그가 적어서 실전에서 안정적이다.

오늘 정리 포인트:

• 그래프에서 “존재 여부” 문제는 종료 조건을 빠르게 잡는 DFS 백트래킹이 강력하다.
• 투 포인터는 정렬된 배열에서 포인터 이동 근거를 명확히 이해하면 구현이 짧고 실수도 줄어든다.

내일도 서로 다른 유형 2문제를 섞어 기본기 루틴을 이어가겠다.