[코드트리][백트래킹] 단순한 동전 챙기기 : Medium(Feat. DFS 관점 바꾸기)

방향 DFS로 풀려던 문제를 조합 DFS로 바꿔본 과정!! 

처음 이 문제를 봤을 때는 격자에서 S부터 출발해 상하좌우로 이동하면서 동전을 줍고, 3개를 주운 뒤 E까지 도착하는 문제라고 생각했다.

그래서 자연스럽게 다음과 같은 DFS를 떠올렸다.

dfs(현재 위치, 마지막으로 먹은 동전 번호, 먹은 동전 개수, 이동 횟수)

 

상하좌우 네 방향으로 이동하면서, 현재 칸에 있는 동전 번호가 이전에 먹은 동전보다 크면 먹고, 아니면 그냥 지나가는 방식이다.

처음에는 이 방식이 직관적이고 정석이라 생각했다...

 

1. 처음 접근: 방향 DFS

처음 풀이에서는 다음과 같은 상태를 관리했다.

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean[][][] visited;

 

상하좌우 방향으로 이동하면서 방문 여부를 체크하고, 동전을 먹을 수 있으면 먹는 방식이었다.

대략적인 흐름은 이렇다.

for (int dir = 0; dir < 4; dir++) {
    int ni = i + dx[dir];
    int nj = j + dy[dir];

    if (범위 밖이면 continue)
    if (방문한 상태면 continue)

    if (map[ni][nj] > prevCoin) {
        dfs(map[ni][nj], coinCnt + 1, cnt + 1, ni, nj);
    } else {
        dfs(prevCoin, coinCnt, cnt + 1, ni, nj);
    }
}

 

이 방식은 문제를 그대로 시뮬레이션한다는 점에서는 이해하기 쉽다.하지만, 결과는 시간초과... 두둥....

 

어떻게 풀지 생각해보니 이 문제에는 중요한 특징이 있다. 격자에 장애물이 없다!!! 이동하는 비용도 똑같다!!!

즉, 어떤 위치에서 다른 위치로 가는 최단 거리는 항상 맨해튼 거리로 구할 수 있다.

Math.abs(r1 - r2) + Math.abs(c1 - c2)

 

즉, 지점과 지점 사이의 최단 거리를 직접 DFS나 BFS로 찾지 않아도 된다는 뜻이다!

 

그렇다면 이 문제의 핵심은 “어떻게 이동할 것인가?”가 아니라 "증가하는 번호의 동전 3개를 어떤 순서로 고를 것인가?"이다. 

 

2. 관점 전환: 이동 DFS → 동전 선택 DFS

문제를 다음과 같이 바꿔볼 수 있다.

1. S에서 시작한다.
2. 번호가 증가하는 동전 3개를 고른다.
3. S → 동전1 → 동전2 → 동전3 → E 의 거리를 계산한다.
4. 그중 최솟값을 구한다.

 

예를 들어 선택한 동전이 2, 5, 8이라면 전체 거리는 다음과 같다.

S → 2번 동전
2번 동전 → 5번 동전
5번 동전 → 8번 동전
8번 동전 → E

 

각 구간은 맨해튼 거리로 계산하면 된다.

dist(S, 2) + dist(2, 5) + dist(5, 8) + dist(8, E)

 

 

2. 개선한 DFS 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static boolean[] nums;
    static Map<Integer, Point> map;

    static int min;
    static int ei, ej;
    static int si, sj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        nums = new boolean[10];
        map = new HashMap<>();

        si = -1;
        sj = -1;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();

            for (int j = 0; j < N; j++) {
                char ch = str.charAt(j);

                if (ch == 'S') {
                    si = i;
                    sj = j;
                } else if (ch == 'E') {
                    ei = i;
                    ej = j;
                } else if ('1' <= ch && ch <= '9') {
                    int num = ch - '0';
                    nums[num] = true;
                    map.put(num, new Point(i, j));
                }
            }
        }

        if (map.size() < 3) {
            System.out.println(-1);
            return;
        }

        min = Integer.MAX_VALUE;

        dfs(1, 0, 0, si, sj);

        System.out.println(min);
    }

    static void dfs(int index, int coinCnt, int cnt, int prevI, int prevJ) {
        if (min <= cnt) {
            return;
        }

        if (coinCnt == 3) {
            min = Math.min(min, cnt + dist(prevI, prevJ, ei, ej));
            return;
        }

        for (int num = index; num <= 9; num++) {
            if (!nums[num]) continue;

            Point p = map.get(num);

            dfs(
                num + 1,
                coinCnt + 1,
                cnt + dist(prevI, prevJ, p.i, p.j),
                p.i,
                p.j
            );
        }
    }

    static int dist(int i1, int j1, int i2, int j2) {
        return Math.abs(i1 - i2) + Math.abs(j1 - j2);
    }

    static class Point {
        int i;
        int j;

        Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

 

4. 기존 방향 DFS와의 차이

처음 접근은 다음과 같았다.

격자를 직접 이동하면서 가능한 모든 경로를 탐색한다.

 

하지만 바꾼 접근은 다음과 같다.

동전 3개를 먼저 고르고, 각 구간의 최단 거리를 계산한다.

 

두 방식의 차이를 정리하면 이렇다.

 

동전 번호는 1~9이므로 최대 9개만 존재한다. 따라서 가능한 조합 수는 최대 다음과 같다.

9C3 = 84

 

즉, 모든 경우를 확인해도 매우 작다.

---

5. 이 풀이에서 얻은 포인트

이번 문제에서 가장 중요한 포인트는 단순히 DFS를 쓰는 것이 아니었다.

처음에는 격자 문제라서 자연스럽게 상하좌우 이동 DFS를 떠올렸다.
하지만 문제를 다시 보면 장애물이 없기 때문에 실제 이동 경로를 탐색할 필요가 없었다.

결국 이 문제는 “길 찾기”라기보다 “증가하는 동전 3개 선택하기”에 가까웠다.

그래서 탐색 대상을 다음과 같이 바꿀 수 있었다.

칸 이동 경로 탐색
→ 동전 조합 탐색

 

이 관점 전환 덕분에 코드가 더 짧아지고, 상태 관리도 단순해졌다.