[SWEA] 1247 최적경로 - JAVA

1. 문제

SW Expert Academy

김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다.
회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100) 두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.
회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다.
회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.
회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,
회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

---

2. 풀이

Points 클래스

클래스 하나를 만들었다. 간단하게 x, y가 들어가는 생성자, 다른 객체와의 거리를 계산하는 메서드가 있다.

class Points {
   int x;
   int y;

   Points(String x, String y) {
      this.x = Integer.parseInt(x);
      this.y = Integer.parseInt(y);
   }

   int getDistance(Points o) {
      return Math.abs(this.x - o.x) + Math.abs(this.y - o.y);
   }
}

 

메인함수

회사, 집을 분리해서 받고 나머지 고객들을 배열에 저장한다. 집과 고객만 static으로 선언했다.

static Points[] clients;
static int N, MIN;
static Points home;

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

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

   for (int tc = 1; tc <= T; tc++) {
      N = Integer.parseInt(in.readLine());
      clients = new Points[N];
      MIN = Integer.MAX_VALUE;

      st = new StringTokenizer(in.readLine());

      Points company = new Points(st.nextToken(), st.nextToken());
      home = new Points(st.nextToken(), st.nextToken());
      for (int i = 0; i < N; i++) clients[i] = new Points(st.nextToken(), st.nextToken());

      dfs(0, company, 0, 0);

      sb.append("#").append(tc).append(" ").append(MIN).append("\n");
   }

   System.out.print(sb);

}

 

최소거리 탐색 메서드

합계가 이미 최소값보다 크다면 중단한다.

cnt==N이라면 다 방문했으므로 (sum+마지막 고객과 집과의 거리)와 최소값을 비교한다.

방문한 고객이 아니라면 다음 고객을 방문해야한다. 지금 clients[i]를 prev값으로 넘기고, sum에도 거리를 저장한다. (재귀호출)

private static void dfs(int cnt, Points prev, int sum, int flag) {
   if (sum >= MIN) return;

   if (cnt == N) {
      MIN = Math.min(MIN, sum + home.getDistance(prev));
      return;
   }

   for (int i = 0; i < N; i++) {
      if ((flag & 1 << i) != 0) continue;
      dfs(cnt + 1, clients[i], sum + prev.getDistance(clients[i]), flag | 1 << i);
   }
}

---

3. 결과