[SWExpertAcademy] 1247. 최적 경로 (자바)
[SWExpertAcademy] 1247. 최적 경로
문제
풀이
순열 문제
방문해야할 곳을 순서를 바꿔가며 모든 케이스를 확인
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
//1247. [S/W 문제해결 응용] 3일차 - 최적 경로 -> 순열
public class SWEA1247 {
static int homeX,homeY,target[][],answer,N;
//방문 여부
static boolean[]visited;
//거리 계산
static int getDis(int x1,int y1,int x2,int y2) {
return Math.abs(x1-x2)+Math.abs(y1-y2);
}
static void visit(int depth,int x,int y,int curDis) {
//현재값이 최소 이동 거리보다 크면 더 갈 필요 X
if(answer<=curDis) return;
//모든 집 다 방문
if(depth==N) {
answer=Math.min(curDis+getDis(x, y, homeX, homeY), answer);
return;
}
for(int i=0;i<N;i++) {
if(!visited[i]) {
visited[i]=true;
visit(depth+1,target[i][0],target[i][1],curDis+getDis(x, y, target[i][0], target[i][1]));
visited[i]=false;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for(int t=1,T=Integer.parseInt(br.readLine());t<=T;t++) {
answer=Integer.MAX_VALUE;
N=Integer.parseInt(br.readLine());
visited=new boolean[N];
st=new StringTokenizer(br.readLine());
int officeX=Integer.parseInt(st.nextToken());
int officeY=Integer.parseInt(st.nextToken());
homeX=Integer.parseInt(st.nextToken());
homeY=Integer.parseInt(st.nextToken());
target=new int[N][2];
for(int i=0;i<N;i++) {
target[i][0]=Integer.parseInt(st.nextToken());
target[i][1]=Integer.parseInt(st.nextToken());
}
visit(0,officeX,officeY,0);
sb.append("#"+t+" "+answer+"\n");
}
bw.write(sb.toString());
bw.flush();
}
}
Author And Source
이 문제에 관하여([SWExpertAcademy] 1247. 최적 경로 (자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jihun333/SWExpertAcademy-1247.-최적-경로-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)