[SWEA] #1247 - 최적경로

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려 한다.

회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)

두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.

여기서 |x|는 x의 절댓값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다.

회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.

회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,

회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

 

💡 아이디어

---

DFS를 이용한 완전 탐색을 이용하면 문제를 쉽게 해결할 수 있다.

먼저 회사에서 한 집을 방문했다면 방문했다고 표시를 한 후 다음 방문하지 않은 집을 재귀 호출을 통해 방문한다.

모든 집을 방문했다면 이전의 거리의 합과 비교해 더 작은 값을 거리의 합으로 경신한다.

이 과정을 재귀 호출로 반복해 모든 경우의 수를 따져보면 최소 거리를 구할 수 있다.

 

💡 소스코드

---

package SWEA;

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

public class SWEA_P1247_최적경로 {
	static int N;
	static int[][] loc;
	static boolean[] visited;
	static int min;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1247_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());
			loc = new int[N + 2][2];// 좌표들을 저장하는 배열
			visited = new boolean[N + 1];// 방문한 곳을 나타내기 위한 배열
			min = Integer.MAX_VALUE;// 최소거리를 찾기 위한 변수

			sz = new StringTokenizer(br.readLine());

			// 배열 처음엔 회사의 좌표
			loc[0][0] = Integer.parseInt(sz.nextToken());
			loc[0][1] = Integer.parseInt(sz.nextToken());

			// 배열 마지막엔 집의 좌표
			loc[N + 1][0] = Integer.parseInt(sz.nextToken());
			loc[N + 1][1] = Integer.parseInt(sz.nextToken());

			// 배열 사이에는 방문하는 집들의 좌표
			for (int i = 1; i <= N; i++) {
				loc[i][0] = Integer.parseInt(sz.nextToken());
				loc[i][1] = Integer.parseInt(sz.nextToken());
			}

			solve(0, loc[0][0], loc[0][1], 0);
			System.out.println("#" + TC + " " + min);
		}
		br.close();
	}

	public static void solve(int cnt, int x, int y, int len) {
		if (cnt == N) {// 전체 집을 다 돌았으면
			len += calc(x, y, loc[N + 1][0], loc[N + 1][1]);// 마지막에 집과의 거리를 더해주고
			if (len < min)// 그게 min보다 작으면 min을 갱신
				min = len;

			return;
		}

		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {// 방문하지 않았다면
				visited[i] = true;// 방문했다고 표시하고
				solve(cnt + 1, loc[i][0], loc[i][1], len + calc(x, y, loc[i][0], loc[i][1]));// 현재 위치를 시작으로 거리를 더해간다
				visited[i] = false;// 다 돌았으면 다시 재귀를 돌 수 있게 false로 바꿔줌
			}
		}
	}

	// 거리를 구하는 method
	public static int calc(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}

}

 

💡 결과

---

완점탐색의 경우 시간은 절대 효율적이지 않은 것 같다...

이 문제는 기초적인 DFS + 완전 탐색으로 아직 DFS + 완전 탐색이 익숙하지 않은 사람에게 괜찮은 문제인 것 같다.