[BOJ] 10971 외판원 순회 2

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

모든 도시를 한 번씩만 순회하여 시작 도시로 돌아오는 비용의 최소값을 구하는 문제.

 

1/ 조건

1) 도시의 숫자는 2~10.

2) [임의의 시작 도시 -> (시작 도시를 제외한 모든 도시를 한 번씩) -> 시작 도시]의 구조.

3) adj_matrix[i][j]와 adj_matrix[j][i]의 값은 다를 수 있다.

4) 길이 놓이지 않은 도시는 그 비용을 0으로 둔다.

5) 해당 도시로 갈 수 있는 경우 비용은 1000000 이하의 양의 정수다.

6) 순회할 수 없는 경우는 주어지지 않는다.

 

2/ 설계

사실 Java를 연습하기 위해 난이도를 보고 고른 문제였다. 입력이 가중치 인접행렬로 들어오는 것을 보고 바로 '재귀를 이용해서 브루트 포스로 풀어야겠다'고 생각했다. 책정된 난이도에 따르면 다른 풀이가 필요하진 않을 거라고 판단한 것.

따라서 시간 초과는 생각하지 않았다. '아마 브루트 포스로 풀라고 낸 문제겠지, 시간 초과가 나오면 그때 가서 전략을 수정하자' 같은 안일한(ㅎㅎㅈㅅ) 마음가짐으로 달려들었다.

굳이 사후 설계를 하자면 도시의 수가 최대 10개이므로 10!의 경우의 수가 생기는데 대충 400만이다. 시간 제한이 2초이므로 브루트 포스라는 접근에 문제는 없을 것이다.

 

3/ 구현

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

public class Main {
    static int n, minCost;
    static int[][] costData;
    public static void dfs(boolean[] visited, int start, int now, int depth, int nowCost) {
        if (minCost < nowCost) return;  // 비용이 양수밖에 없으므로 가지치기

        if (depth == n-1 && costData[now][start] != 0) {
            nowCost += costData[now][start];            // 모든 도시를 순회 후 시작 도시로 돌아가는 비용 더하기
            if (minCost > nowCost) minCost = nowCost;   // 최소 비용 갱신
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i] && costData[now][i] != 0) { // 방문하지 않았거나 길이 놓인 경우에만 진행
                visited[i] = true;
                dfs(visited, start, i, depth + 1, nowCost + costData[now][i]);
                visited[i] = false;
            }
        }
    }

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

        n = Integer.parseInt(br.readLine());
        costData = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                costData[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        boolean[] visited = new boolean[n];
        minCost = 10000000;  // 최대 10개의 도시가 1,000,000의 비용을 가질 수 있으므로
        for (int start = 0; start < n; start++) {
            visited[start] = true;
            dfs(visited, start, start, 0, 0);
            visited[start] = false;
        }

        System.out.print(minCost);
    }
}

 

4/ 결과

야호!

 

5/ 후기

1) 어제부터 Java로 기초 문제를 풀기 시작했다. 아주 쉬운 사칙연산이나 입출력 문제들을 풀고 나서 오늘 곧바로 이 문제에 도전했는데 쉽지 않았다……. Python에서는 간단했던 것들이 조금 더 복잡해졌는데, 특히 자료형을 지정하는 부분에서 자주 버벅였다. Python에서는 자동적으로 형변환을 해주므로 최대값이나 최소값을 ±21e8로 퉁치고 넘어가곤 했지만 Java에서는 변수는 물론 함수의 반환 자료형까지 정확히 지정을 해줘야만 하는 게 Python만 해온 내 입장에선 까다롭게 느껴졌다. 이러한 엄격함이 견고함을 가져온다고는 생각하지만 쉽지가 않다. 익숙해져야겠지…….

 

2) 첫 풀이에서는 minCost를 double 자료형으로 두고 초기값으로 21e8을 대입한 뒤 출력할 때 명시적으로 형변환을 해주었다. 그리고 포스팅을 하기 직전에 문제의 조건에 따라 비용이 가질 수 있는 최대값(10000000)으로 minCost의 초기값을 설정하는 방식으로 코드를 수정했다.

사실, 21e8을 쓰는 쪽이 틀릴 여지가 더 적지 않나 싶다. 아예 2^31보다 큰 입출력이 상정되면 이야기가 다르겠지만, 일반적으로 봤을 때 '이론적으로 가능한 최대/최소값'을 고려하다가 틀리는 경우가 더 많을 것 같다. 자원이 그다지 들지 않는다면 통계적-확률적으로 안전한 길을 선택하는 것이 옳아보인다. 고민은 더 해봐야 할 듯.

 

3) 풀기 전에는 가지치기 생각을 분명히 했는데 한땀한땀 코드를 쳐서 그런지 다 잊어버렸다. 가지치기 코드 한 줄을 넣고 안 넣고 차이가 정확히 2배 차이가 났다(당연히 세부 사항은 테스트케이스 따라 다르겠지만) . 손으로 설계를 하는 능력이 제일 중요하지만 머릿속에서 떠오른 풀이를 바로 구현하는 데에도 익숙해져야 한다고 보는데 정말 쉽지가 않다. 사람은 망각의 동물… 기록을 해야 한다… 하지만…….

 

4) 포스팅을 하면서 다른 풀이를 생각해봤는데, 가장 먼저 떠오른 것은 플로이드-워셜이었다. 가중치 인접행렬과 최소 비용이라는 키워드 때문에. 하지만 플로이드-워셜에서 선정된 최단거리가 이미 지나온 도시를 포함하고 있을 가능성이 있었다. 다른 방식이 있을까? 검색해보니 DP를 쓸 수도 있다고 한다. 그게 되나…?

일부러 자세한 내용을 읽지 않고 머리만 굴려봤는데 판단이 잘 서지 않았다. 특정 도시들에 들리지 않았을 때 그 도시들을 경유하는 최소 비용을 구할 수는 있겠지만 그게 의미가 있을까? 아마 BOJ에 입력값이 더 큰 외판원 문제가 있을 테니 그 문제를 만났을 때 고민을 마저 이어가는 것으로.

 

5) Java로 나름 제대로 된 문제를 처음 풀어봤다는 데에는 의미가 있지만, '그냥 그럴 거 같애서 브루트 포스로 풀었읍니다ㅎ'라고 말하는 것 조금 부끄러운 일인 것 같다. 출제자의 의도-어떤 알고리즘을 요구하는지-를 사전에 검증하는 것이 굉장히 중요한데 그런 측면이 부족하구나 싶고. 물론 재미와 흥미를 유지하는 것도 중요하고 사람이 당장 나아지기가 힘들기 때문에 지금은 이러한 포스팅으로 만족한다. 블로그 등지에서의 사후 정리가 발전의 계기가 됐으면 좋겠다!