[SW Expert Academy] 1247. 최적 경로 - D5 / Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD

SW Expert Academy

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

public class Solution {

	static int N, visit[][], min, officeR, officeC, houseR, houseC;

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

		int T = Integer.parseInt(br.readLine());  // 전체 테스트 케이스의 수
		for (int testCase = 1; testCase <= T; testCase++) {
			N = Integer.parseInt(br.readLine()); // 고객 수
			visit = new int[N][2];

			// 회사의 좌표,집의 좌표, N명의 고객의 좌표
			StringTokenizer st = new StringTokenizer(br.readLine());
			officeR = Integer.parseInt(st.nextToken());
			officeC = Integer.parseInt(st.nextToken());
			houseR = Integer.parseInt(st.nextToken());
			houseC = Integer.parseInt(st.nextToken());

			for (int i = 0; i < N; i++) {
				visit[i][0] = Integer.parseInt(st.nextToken());
				visit[i][1] = Integer.parseInt(st.nextToken());
			}

			min = Integer.MAX_VALUE;
			visit(0, 0, 0, officeR, officeC); // Office부터 고객 집 방문하기
			sb.append("#").append(testCase).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}

	private static void visit(int cnt, int sum, int flag, int r, int c) {
    	// 방문한 집 count, 거리 합, 방문한 집 체크, 현재 r, 현재 c
    
    		// N개의 집 모두 방문했을 경우 마지막 고객의 집에서 자신의 집까지의 거리 더해서 최솟값 구하기
		if (cnt == N) {
			min = Math.min(min, sum + getDistance(r, c, houseR, houseC));
			return;
		}
        
		if (sum > min) {
			return;
		}

		for (int i = 0; i < N; i++) {
			if ((flag & (1 << i)) != 0) {
				continue;
			}
			visit(cnt + 1, sum + getDistance(r, c, visit[i][0], visit[i][1]), (flag | (1 << i)), visit[i][0],
					visit[i][1]);
		}
	}

	public static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}
}