SWEA[1247] - 최적 경로

링크

SWEA[1247]

문제설명

• 조합, 완전탐색

문제풀이

• 조합, 완전탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {

    public static int length(int[] a, int[] b) {
        return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
    }

    public static int Ans=Integer.MAX_VALUE;
    public static int Temp;
    public static int[][] rc;
    public static int[] work;
    public static int[] home;
    public static int N;

    public static int[] comb;

    public static void Simulation() {
        Temp=0;
        Temp+=length(work,rc[comb[0]]);
        for (int i = 0; i < N-1; i++) {
            Temp+=length(rc[comb[i]],rc[comb[i+1]]);
            if(Temp>Ans) {    //백트래킹?
                return;
            }
        }
        Temp+=length(rc[comb[N-1]],home);
        if(Ans>Temp) {
            int debug=0;
        }
        Ans = Math.min(Ans, Temp);
    }

    public static void Search(int cnt, int flag) {
        if(cnt==N) {
            //System.out.println(Arrays.toString(comb));
            Simulation();
            return;
        }
        for (int i = 0; i < N; i++) {
//            겹치는게 없을 경우
            if((flag & 1<<i)==0) {
                comb[cnt]=i;
                Search(cnt+1,flag | 1<<i);
            }
        }
    }

    public static void main(String args[]) throws Exception
    {
        //System.setIn(new FileInputStream("res/swea/1247.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(br.readLine().trim());
            rc = new int[N][2];
            comb = new int[N];
            work = new int[2];
            home = new int[2];

            st = new StringTokenizer(br.readLine());
            work[0] = Integer.parseInt(st.nextToken());
            work[1] = Integer.parseInt(st.nextToken());
            home[0] = Integer.parseInt(st.nextToken());
            home[1] = Integer.parseInt(st.nextToken());
            for (int i = 0; i < N; i++) {
                rc[i][0] = Integer.parseInt(st.nextToken());
                rc[i][1] = Integer.parseInt(st.nextToken());
            }


            Search(0, 0);

            System.out.println("#"+test_case+" "+Ans);
//            초기화
            Ans=Integer.MAX_VALUE;
        }
    }
}

아쉬운점

• 문제 잘못읽어서 인풋 제대로 못읽음 ㅡㅡ
  • 회사, 집, N개의 방문지 순서임...
  • N개의 방문지, 회사, 집 순서로 했었음
• 백트래킹은 어떻게하는건지 모르겠음

잘한점

• bit masking으로 조합 만듬
• O(N) = 10! = 36만 완전탐색 가능