1247번 - 최적 경로

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간
4. 우리 반 1등 코드와의 차이
5. 싸피 1등 코드와의 차이

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

최단 경로로 모든 노드를 방문했을 때 그 경로의 길이를 구하는 문제이다.

단, 문제에 몇 가지 주목할 만한 조건이 붙는다.

 

• 방문해야 하는 고객(노드)의 수가 최대 10명이다.

N이 10 이하인 경우는 완전 탐색으로 풀 수 있지만

그 이상은 DP를 적용해야 한다.

즉, 이 문제에는 완전탐색으로 풀이가 가능하다는 것이다.

 

• 이 문제는 가장 짧은 경로를 '효율적으로' 찾는 것이 목적이 아니다.
• 모든 가능한 경로를 살펴서 해를 찾아도 좋다. => (완전 탐색)

문제에서는 친절하게 완전 탐색을 사용하라고 대놓고 힌트를 던져주고 있다.

물론 더 효율적으로 풀 수 있겠지만 제출자의 의도는 그게 아닌 듯하다.

그래서 나도 그냥 완전탐색을 사용하기로 했다.

 

• 회사에서 출발하여 고객을 모두 방문한 뒤 집으로 돌아간다.

그다음 염두에 두어야 할 조건은 위와 같다.

항상 출발은 회사에서, 도착은 집으로 해야 한다는 조건이다.

이 조건을 잘 활용하면 완전 탐색의 소요시간이 확 줄어들게 된다.

 

 

2. 코드

public class Day11_1247_최적경로 {
	static int N;
	static int shortestRoute;
	static boolean[] visited;
	static int[][] map;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringTokenizer st;

		for (int tc = 1; tc <= testCase; tc++) {
			N = Integer.parseInt(br.readLine()) + 2; // 회사와 집까지 카운트 하기 위해 + 2
			map = new int[N][N]; // 거리
			int[][] xy = new int[N][2]; // 좌표
			visited = new boolean[N]; // 방문여부

			// 좌표 저장
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				xy[i][0] = Integer.parseInt(st.nextToken());
				xy[i][1] = Integer.parseInt(st.nextToken());
			}

			// 거리 저장
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					int dist = Math.abs(xy[i][0] - xy[j][0]) + Math.abs(xy[i][1] - xy[j][1]);
					map[i][j] = dist;
				}
			}

			shortestRoute = Integer.MAX_VALUE;
			visited[0] = true;
			dfs(0, 1, 0);

			System.out.println("#" + tc + " " + shortestRoute);
		}
	}

	public static void dfs(int from, int cnt, int dist) {
		if (from == 1) { // 집에 도착한 경우
			if (cnt == N) { // 고객을 다 방문하고 도착한 경우
				if(dist < shortestRoute) {
					shortestRoute = dist;
				}
			} else { // 방문도 다 안했는데 집으로 왔어?
				return; // 안돼. 돌아가.
			}
		}

		for (int i = 0; i < N; i++) {
			if(!visited[i] && map[from][i] != 0 && dist + map[from][i] < shortestRoute) {
				visited[i] = true;
				dfs(i, cnt + 1, dist + map[from][i]);
				visited[i] = false;
			}
		}
	}
}

좌표를 먼저 이쁘게(?) 잘 저장하고

좌표끼리의 거리를 map 배열에 저장하고

dfs를 돌면서 방문하는 모든 경우의 수를 탐색했다.

 

if(!visited[i] && map[from][i] != 0 && dist + map[from][i] < shortestRoute)

이 부분이 가장 중요하다.

더 이상 탐색할 가치가 없을 때 탐색을 중단하고 다음을 진행하는 '가지치기'를 해주는 작업이다.

 

 

가지치기 전(아래) / 가지치기 후(위)

 

위 실행 결과는 똑같은 코드에 'dist + map[from][i] < shortestRoute' 조건을 넣냐 안 넣냐에 따른 실행결과이다.

실행시간이 거의 9배나 차이 나는 것을 알 수 있다.

이전에 탐색했던 최단경로보다 현재 탐색 중인 경로의 길이가 길어지면 더 이상 탐색을 하지 않겠다는 조건이다.

더 이상 탐색할 가치가 없기 때문이다.

 

이렇게 DFS + 가지치기가 합쳐진 알고리즘을 백트래킹(Backtracking)이라고 한다.

가지치기를 어떻게 해야 할지, 그 조건에 대해서는 문제마다 천차만별이므로 직접 찾아야 한다.

즉, 이 문제의 의도는 "DP를 사용해서 효율적인 코드를 짜 보세요"가 아니라

"가지치기 조건을 찾아 백트래킹을 사용해보세요"였던 것

 

 

3. 실행시간

저도 1등 시켜줘요 광광

 

오늘도 1등을 못했다.

포인트를 사용해 1등의 코드를 합법적 해부를 해보자.

 

 

4. 우리 반 1등 코드와의 차이

 

내 소듕한 포인트...

 

포인트를 희생해 얻은 결과는 다음과 같다.

 

• 나는 회사, 집을 포함해서 모든 좌표를 한 곳에 저장했지만 이 친구는 회사, 집을 따로 저장했다.
  • 나는 회사, 집을 포함해서 N + 2번 dfs를 돌았고 이 친구는 N번 dfs를 돌았다. (물론 내가 if문으로 가지치기를 했지만 이것 때문에 시간 차이가 많이 난 것 같다)
• 나는 좌표 간의 거리를 계산해서 배열에 저장한 다음 사용했고 이 친구는 따로 저장하지 않고 필요할 때 계산해서 썼다.
  • 저장을 하지 않으면 매번 같은 거리를 다시 계산하므로 손해다. 속도면 / 가독성면에서 저장을 하고 사용하는 것이 낫다.
• 나는 메인 문에서 dfs 사용하기 전에 visited[0] = true로 주고 dfs 안에서도 true/false를 주는 구문이 있는데 이 친구를 보니까 dfs의 첫 시작부분에서 true를 주면 visited[0] = true를 dfs 호출 전에 안 해줘도 된다.
  • 그냥 자잘한 부분인데 주워 먹을만한 것 같아서 줍줍

 

 

5. 싸피 1등 코드와의 차이

와 미친거 아니야?

 

갑자기 궁금해져서 싸피 1등 코드는 얼마나 빠를까 검색해봤다.

와. 당신 사람입니까?

휴먼? 미치셨습니까?

 

2등 하신 분은 코드 길이 보니까 그냥 답만 출력한 거 같고.

아니 1등분은 답만 출력한 사람보다 더 빠르다고요?

내 뇌로는 도저히 이해가 가지 않는다. 부검을 해봐야겠어.

 

 

공부 좀 하겠다는데 거 너무한거 아니오?

 

...

왜 때문에 더 비싸진 거죠 포인트가...

비싼 코드다 이건가.

그냥 보지 말까 고민하다가 너무 궁금해서 질러봤다.

포인트를 희생해 얻은 결과는 다음과 같다.

 

• 이 분은 BufferedReader와 BufferedWriter를 활용하셨다. (실행시간 단축 영끌)
• 좌표를 저장하기 위해 Node라는 클래스를 만듦
  • 위 2개는 속도에 엄청난 영향을 주지 않았을 것 같다.
• 그리고 가장 중요한 로직 부분에는... 쉬프트 연산과 &연산을 활용해서... 한마디로 나는 일반적인(?) 수학 계산을 했는데 그걸 비트 연산으로 계산을 하셨다는 건데... 어 그니까 음... 어...

 

혼자 있을래요...

 

나는 개발자가 되려면 멀었나 보다

코드를 봐도 이해가 안 가고 어떻게 이런 발상을 해서 코드를 짰는지 신기할 따름이다.

진짜 사람 맞나? 알파고가 짠 거 아니야?

 

 

 

 

 

---

💡 느낀 점

• 세상은 넓고 괴물은 많다.
• 비트 연산이 엄청나게 빠른 거구나...
• 컴퓨터가 빨리 알아들을 수 있게 하려면 컴퓨터 언어에 가깝게 말해야지.. 그치..
• 싸피 1등 코드는 이제 열람 안 해야겠다. 넘사벽인 것 같다.

---