[Java] SWEA-D5. 1247. 최적 경로

문제 정보

```

플랫폼	SW Expert Academy
문제	1247. 최적 경로
난이도	D5
언어	Java
문제 링크	문제 바로가기 →

```

1. 문제 요약

김대리가 회사에 출발해 냉장고 배달을 한다.

N명의 고객 모두 방문한 후 자신의 집으로 가야 한다.

두 위치 사이의 거리(x1, y1) , (x2, y2)가 주어졌을때의 거리는 |x1-x2| + |y1-y2|로 구할 수 있습니다.

회사 -> N명 -> 집 이렇게 모든 고객을 방문해야 합니다.

 

 

  

2. 아이디어

N이 작아서, 모든 경우를 탐색하는 재귀를 활용해도 좋을 것 같다.
반복적으로 recursive함수를 호출할 때 1-2-3 -> 1-2-1 이렇게 이전에 방문한 고객의 집을 재방문하지 말아야 한다!
-> 중복x
-> visited[] 배열 활용해서 중복 탐색 방문 방지!
고객들을 방문하는 순서는 자유롭고, 아직 방문하지 않은 고객을 하나씩 선택하며 모든 순서를 탐색해야 한다.
고객을 선택할 때마다 거리를 계산해 나가야하는데, 해당 재귀가 끝난 후에도 반복적으로 다른 고객들을 탐색해야 합니다.
-> 이전에 누적으로 증가했던 거리를 되돌려야 합니다.(백트래킹)

재귀를 사용해서, 고객의 집을 탐색해야하는데, 이전에 간 집은 탐색하지 않아도 됩니다.

 

그리고 시작은 회사, 최종 도착지는 집 이렇게 지정되어야 합니다.

 

3. 주의할 점

좌표를 입력받을 때 첫 번째 좌표는 회사, ​두 번째 좌표는 집이라는 점을 반드시 고려해야 합니다.

모든 고객을 방문한 뒤에는 탐색을 종료하는 것이 아니라, 현재 위치에서 집까지의 거리를 추가하여 최종 이동 거리를 계산해야 합니다.

4. 풀이 코드

class Solution {
    public static int ans = Integer.MAX_VALUE;
    
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int numberOfTestCases = sc.nextInt();
        
        for(int testCase=1; testCase<=numberOfTestCases; testCase++) {
            ans = Integer.MAX_VALUE;
            int clients = sc.nextInt();
            int[][] points = new int[clients+2][2];
            for(int i = 0;i<clients+2;i++) {
                for(int j = 0; j<2;j++) {
                    points[i][j] = sc.nextInt();
                }
            }
             
            dfs(points, new boolean[clients+2], 0, 2, 0);
            System.out.printf("#%d %d\n", testCase, ans);
        }
    }
     
    static int dist(int x1,int y1,int x2, int y2) {
        return Math.abs(x1-x2)+Math.abs(y1-y2);
    }
     
    //프로그램은 가장 짧은 경로의 이동거리만 밝히면
    // 중복x
    static void dfs(int[][] points, boolean[] visited, int selectedCnt, int selectedIdx, int sum) {
        int n = points.length;
         
        if (selectedCnt == n-2) {
            int[] lastNode = points[selectedIdx];
            int[] home = points[1];
            ans = Math.min(ans,sum + dist(lastNode[0], lastNode[1], home[0],home[1]));
            return;
        }
         
        for(int i=2;i<n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int[] prevNode = points[selectedIdx];
                int[] curNode = points[i];
                if (selectedCnt==0) prevNode = points[0];        
                dfs(points, 
                        visited, 
                        selectedCnt+1,
                        i,
                        sum + dist(prevNode[0], prevNode[1], curNode[0], curNode[1]));
                visited[i] = false;
            }   
        }
        return;
    }
}

 

4. 시행착오

시행착오 #1

처음에는 DFS에서 반복문의 시작 인덱스를 selectedIdx로 설정하여 탐색했습니다.

하지만 이미 visited[] 배열을 통해 방문 여부를 관리하고 있기 때문에, 반복문의 시작 위치를 selectedIdx로 제한할 필요가 없습니다.

오히려 이렇게 하면 현재 인덱스보다 앞에 있는 아직 방문하지 않은 고객을 선택할 수 없어 일부 경우의 수를 탐색하지 못하게 됩니다.

 

이 문제는 조합이 아니라 순열을 구하는 문제이므로, 매 재귀 호출마다 모든 고객을 대상으로 반복문을 수행하고, visited[]를 이용해 이미 방문한 고객만 건너뛰어야 합니다.

 

즉, 반복문과 재귀를 함께 사용할 때 백트래킹의 핵심은 반복문의 시작 인덱스가 아니라 visited[]를 이용해 상태를 복원하며 모든 경우를 탐색하는 것이라는 점을 놓쳤던 것이었습니다.

 

시행착오 #2

DFS에서는 하나의 재귀 함수 안에서 반복문을 통해 모든 고객을 차례대로 탐색합니다.

 

예를 들어 고객 1을 선택한 뒤 재귀 호출을 통해 고객 2부터 마지막 고객까지 모두 탐색하고 돌아오면, 다시 고객 1을 기준으로 고객 3을 선택하는 경우도 탐색해야 합니다.

하지만 저는 이전 재귀에서 누적했던 sum 값을 원래대로 복원하지 않아, 고객 3을 탐색할 때도 이전 탐색에서 더해졌던 거리가 그대로 누적되는 문제가 발생했습니다.

 

 

즉, 재귀 호출이 끝난 뒤에는 현재 고객까지 더했던 거리만큼 sum을 원래 상태로 되돌려야 하는데, 이 과정을 수행하지 않아 잘못된 결과가 나왔습니다.

 

이는 반복문과 재귀를 함께 사용할 때 상태를 복원하는 백트래킹을 제대로 적용하지 못했던 것이 원인이었습니다.

 

재귀 구조에서는 현재 recursive함수 안에서, 2개 이상의 recursive를 호출할 때는 백트래킹( 위에서 recursive할 때 증가시켰던 상태를 복구 할 것인가) 를 주의 깊게 봐야할 것 같습니다.

재귀 호출이 여러 갈래로 뻗는 구조에서는,(한 함수에서 자기자신을 여러 번 호출할 경우)
한 갈래 탐색에서 변경한 상태를 다음 갈래 탐색 전에 원상복구해야 한다.

5. 복잡도

시간 복잡도: O(N)

```

공간 복잡도: O(N)

```

반복문과 사용한 자료구조를 기준으로 복잡도가 왜 이렇게 나오는지 짧게 작성합니다.

6. 개선할 수 있는 부분

1. dist() 호출 비용 많다.

dist(prevNode[0], prevNode[1], curNode[0], curNode[1])

 

큰 문제는 아니지만, 함수를 호출한다는 것은 method area까지 접근해서 실행 로직을 파악하기 때매.. 이부분은 인라인화를 해야하나..

 

2. 가지는 쳐야 제맛..

 

10! = 3,628,800

경로 모든 탐색

 

-> 현재 탐색중인 가지가 최솟값보다 더 크면 재귀 더 돌 필요x

static void dfs(int[][] points, boolean[] visited, int selectedCnt, int selectedIdx, int sum) {
    if (sum>= ans) return; // 가지 치기
    int n = points.length;
	
    if (cnt==n-2) {
    	ans = Math.min(ans, sum + distance(points[idx], points[1]));
        return;
    }
}

 

 3. 전역 관리

static int N;
static int ans;
static int[][] points;
static boolean[] visited;

static void dfs(int idx, int cnt, int sum) {
	if (sum>=ans) return;
    
    if(cnt==N) {
    	ans = Math.min(ans,sum + distpoints[idx][0], points[idx][1], points[1][0],points[1][1]));
        return;
    }
    
    for(int i=2;i<N+2;i++) {
    	if(!visited[i]) {
        	visited[i] = true;
            dfs(i, cnt+1, sum + dist(
                                  points[i][0], 
                                  points[i][1], 
                                  points[idx][0], 
                                  points[idx][1]);
            visited[i] = false;
        }
    }
}

 

 지금보니 points 2차원 배열로 다루는거보다 1차원 배열 x,y 두개 다루는 것도 좋아보이네요.

 

dfs(0, 0, 0); 이걸 호출하면 되는데, 처음에 문제 풀 때에는 시작지점, 도착지점이 input에서 처음 단계에서 주어져서 이부분을 dfs로직 내부에 넣었습니다.
그런데 dfs 내부 포문이 i == 2로 시작하니까.. i==2일때라는 분기처리를 빼도 될거 같네요. 

7. 회고

```

어려웠던 점

중복x라는 것을 활용하기 위해 재귀를 활용하는것이 떠오름.

여러 가지를 호출해야만 모든 고객에게 방문할 수 있고 방문 후에, 아직 방문하지 않은 그런 고객은 다시 이전의 상태 기반으로 재귀를 해나가는 백트래킹을 써야함.

 

백트래킹을 쓰는데, 선언한 dfs의 매개변수들에 대해서 복구 하는 로직이 잘 들어가지 않았음.

배운 점

재귀 +백트래킹을 쓰고, 가지들을 어떻게 뻗어나갈까 생각해야함.
백트래킹할 때 매개변수들의 복귀 로직도 잘 짜야한다는 것을 알게됨.

다음에 적용할 점

: )

```

한 줄 정리

이 문제의 핵심을 한 문장으로 정리합니다.