[SWEA] 1247. 최적경로
문제
1247. [S/W 문제해결 응용] 3일차 - 최적 경로
회사에서 출발해서 N명의 고객에게 방문하고 자신의 집으로 돌아간다.
이때 회사 -> N명의 고객 전체 -> 집
의 경로 중 총 이동거리가 가장 짧은 경로를 찾아라.
풀이
- 좌표와 방문여부를 저장하는 Cord 클래스 생성
- 회사, 집, 고객들 위치의 좌표를 Cord에 담아 list에 저장
- list[0] : 회사
- list[1] : 집
- list[2] ~ list[N+1] : 고객들의 위치
- DFS로 하나씩 방문
depth == N
이 되면getMinDistance()
를 호출하고 종료 - 4번에서 계속- for문으로 방문하지 않은 좌표를 하나씩 방문함.
- distance에 이동거리를 추가하여(newDistance) 다음 좌표로 이동(재귀)
getMinDistance()
: 방문거리에 (마지막 위치 ~ 집)이동거리를 추가하고, 가장 짧은 경로라면 갱신- 테스트케이스별 출력
자바코드
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
static int N;
static Cord [] list; // 0 office, 1 home, 2~N+2 : customer
static int minDistance=987654321;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
minDistance = 987654321;
N = sc.nextInt();
list = new Cord[N+2];
int r, c;
for (int i=0; i<N+2; i++) {
r = sc.nextInt();
c = sc.nextInt();
list[i] = new Cord(r, c);
}
DFS(list[0], 0, 0);
System.out.printf("#%d %d\n", test_case, minDistance);
}
}
public static void DFS(Cord cur, int distance, int depth) {
if (depth == N) {
getMinDistance(cur, distance);
return;
} else {
int newDistance;
for (int i=2; i<N+2; i++) {
if (list[i].isVisit) continue;
newDistance = distance + Math.abs(cur.r-list[i].r) + Math.abs(cur.c-list[i].c);
list[i].isVisit = true;
DFS(list[i], newDistance, depth+1);
list[i].isVisit = false;
}
}
}
public static void getMinDistance(Cord last, int distance) {
distance += Math.abs(list[1].r - last.r) + Math.abs(list[1].c - last.c);
if (distance < minDistance) {
minDistance = distance;
}
}
static class Cord {
int r;
int c;
boolean isVisit;
Cord(int r, int c) {
this.r = r;
this.c = c;
this.isVisit = false;
}
}
}
개선
- 전처리 (중복되는 연산 저장)
- 백트래킹
Author And Source
이 문제에 관하여([SWEA] 1247. 최적경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@euzl/SWEA-1247.-최적경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)