[Java] SWEA / 최적경로 / 1247번
[Java] SWEA / 최적경로 / 1247번
문제
문제의 저작권은 SW Expert Academy에 있습니다
접근 방식
- 손님의 집 위치를 순열 배열로 만든다
- 회사로부터 해당 배열의 손님 집을 지나 집으로 향하는 경로를 계산하여 최솟값을 저장한다
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Solution_1247_정현명 {
static int T,N;
static int[] company;
static int[] home;
static int[][] customer;
static int minPath;
static int numbers[];
public static void main(String[] args) throws IOException{
// =================== 입력 ====================
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for(int tc=1;tc<=T;tc++) {
N = Integer.parseInt(br.readLine()); // 고객 수
StringTokenizer st = new StringTokenizer(br.readLine());
company = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; // 회사 위치
home = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; // 집 위치
customer = new int[N][2]; // 고객들 위치
for(int i=0;i<N;i++) {
customer[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
}
numbers = new int[N];
minPath = 200 * 11; // 나올 수 없는 최대값
// ==================== 솔루션 ===================
permutation(0,0);
// ==================== 출력 =====================
sb.append("#"+tc+" "+minPath+"\n");
}
System.out.print(sb);
}
// 순열 배열 만들기
public static void permutation(int cnt, int flag) {
if (cnt == N) {
calPath(numbers); // 순열 배열이 만들어지면 해당 배열로 전체 경로길이 계산
return;
}
for(int i=0;i<N;i++) {
if((flag & 1<<i) != 0) continue;
numbers[cnt] = i;
permutation(cnt+1,flag | 1<<i);
}
}
// 경로길이 계산
public static void calPath(int numbers[]) {
int r = company[1];
int c = company[0];
int sumPath = 0;
for(int i=0;i<N;i++) {
int nextR = customer[numbers[i]][1];
int nextC = customer[numbers[i]][0];
sumPath += Math.abs(nextR - r) + Math.abs(nextC - c);
r = nextR;
c = nextC;
}
sumPath += Math.abs(r - home[1]) + Math.abs(c - home[0]);
minPath = Math.min(minPath, sumPath);
}
}
Author And Source
이 문제에 관하여([Java] SWEA / 최적경로 / 1247번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/Java-SWEA-최적경로-1247번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)