내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/118669

등산코스 정하기 문제입니다.

몇 달이 지났지만 코딩 테스트 당시에도 굉장히 급박하게 풀었던 기억이 나는데요. 

우선 정답으로 통과한 아이디어는 이렇습니다.

입구 -> 정상 -> 출발한 입구로 돌아오는 경로의 최대 Intensity를 최소로 만드는 경로를 구해야 합니다. 이는 정상 -> 입구로 가는 경로의 최대 Intensity의 최솟값과 같습니다. (같은 길을 두 번 왕복해도 Intensity는 똑같기 때문입니다.)

N이 5만으로 큰 값이기 때문에 2차원 배열로 만들시 25억 사이즈가 됩니다. 배열 대신 인접리스트로 그래프를 구현하고, 모든 정상에 대해 적절하게 가지치기를 하며 BFS를 돌려 각 입구까지 가는 최대 Intensity의 최소값을 구했습니다.

이제 구한 값들을 비교해 정답을 찾아내면 됩니다.

굉장히 브루트포스 스럽게 풀었고 가지치기를 잘 한 덕에 모든 테케에 통과는 했지만 효율성이나 구현이 깔끔하지 못합니다.

어차피 Python언어로도 다시 풀 예정이기 때문에 조금 더 다듬어서 Java로도 나은 솔루션을 다시 올리도록 하겠습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class q118669_Programmers_등산코스정하기 {
	public static void main(String[] args) {

		int[][] paths = new int[][] { { 1, 2, 3 }, { 2, 3, 5 }, { 2, 4, 2 }, { 2, 5, 4 }, { 3, 4, 4 }, { 4, 5, 3 },
				{ 4, 6, 1 }, { 5, 6, 1 } };
		int[] gates = new int[] { 1, 3 };
		int[] summits = new int[] { 5 };

		System.out.println(Arrays.toString(solution(6, paths, gates, summits)));
	}

	static public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		int[] answer = { -1, 10_000_001 };

		boolean[] gateCheck = new boolean[n + 1];
		boolean[] summitCheck = new boolean[n + 1];

		for (int i = 0; i < gates.length; i++) {
			gateCheck[gates[i]] = true;
		}
		for (int i = 0; i < summits.length; i++) {
			summitCheck[summits[i]] = true;
		}

		ArrayList<ArrayList> pathList = new ArrayList<ArrayList>();

		for (int i = 0; i <= n; i++) {
			pathList.add(new ArrayList<int[]>());
		}

		for (int i = 0; i < paths.length; i++) {
			int from = paths[i][0];
			int to = paths[i][1];
			int dis = paths[i][2];

			pathList.get(from).add(new int[] { to, dis });
			pathList.get(to).add(new int[] { from, dis });
		}

		Arrays.sort(summits);

		for (int i = 0; i < summits.length; i++) {
			Queue<int[]> queue = new LinkedList<int[]>();
			int[] visited = new int[n + 1];
			Arrays.fill(visited, 10_000_001);
			queue.offer(new int[] { summits[i], 0 });
			visited[summits[i]] = 0;
			int minInten = answer[1];

			while (!queue.isEmpty()) {
				int now = queue.peek()[0];
				int maxInten = queue.poll()[1];

				if (maxInten >= minInten) {
					continue;
				}

				ArrayList<int[]> canMove = pathList.get(now);

				for (int j = 0; j < canMove.size(); j++) {
					int to = canMove.get(j)[0];
					int dis = canMove.get(j)[1];
					int nextInten = Math.max(maxInten, dis);

					if (visited[to] > nextInten) {
						if (gateCheck[to]) {
							visited[to] = nextInten;
							minInten = Math.min(nextInten, minInten);
						} else if (!summitCheck[to]) {
							queue.offer(new int[] { to, nextInten });
							visited[to] = nextInten;
						}
					}
				}
			}

			for (int j = 0; j < gates.length; j++) {
				int goal = gates[j];
				if (visited[goal] < answer[1]) {
					answer[0] = summits[i];
					answer[1] = visited[goal];
				}
			}
		}
		return answer;
	}
}

https://www.acmicpc.net/problem/2146

구현을 신경써야 하는 문제입니다.

문제를 2개의 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 다리 만들기

1번은 BFS DFS아무것이나 원하는 방법으로 구현하면 됩니다.

2번의 경우는 BFS를 이용하는것이 구현과 이해가 간편합니다.

시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q2146_BOJ_다리만들기 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int[] parent;
	static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				if (map[n][m] == -1) {
					dfs(n, m, island);
					island++;
				}
			}
		}

		int answer = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][N];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m });
						visit[n][m] = true;
					}
				}
			}

			int l = 0;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {

					int[] now = queue.poll();
					int x = now[0];
					int y = now[1];

					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY]) {

							if (map[nX][nY] == 0) {
								queue.offer(new int[] { nX, nY });
								visit[nX][nY] = true;
							} else {
								answer = Math.min(answer, l);
								visit[nX][nY] = true;
							}
						}
					}
				}
				l++;
				if (l > answer) {
					queue.clear();
				}
			}
		}
		System.out.println(answer);

	}

	static void dfs(int x, int y, int name) {
		map[x][y] = name;

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY) && map[nX][nY] == -1) {
				dfs(nX, nY, name);
			}
		}

	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}
}

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

주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.

Java의 경우에는 모든 경우에 대해 순열을 구하고 그 순열이 조건에 적합한지 검증을 하면서 가지치기를 해도 주어진 실행시간 안에 통과가 되지만, 조금 더 효율적으로 코드를 짤 수 있는 방법들이 있어 3가지를 전부 소개해드리겠습니다.

우선 기본적으로 모든 순열을 만들고, 이후 조건에 맞는 경우를 찾는 코드입니다.

시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고 2^(N-현재 단계)만큼 더해주었습니다.

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

public class q3234_SWEA_준환이의양팔저울 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new int[N], new boolean[N]);

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

		System.out.println(sb);
	}

	static void makePermutation(int count, int[] choosed, boolean[] visited) {
		if (count == N) {
			check(1, choosed, choosed[0], 0);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				choosed[count] = gram[i];
				makePermutation(count + 1, choosed, visited);
				visited[i] = false;
			}
		}
	}

	static void check(int count, int[] choosed, int left, int right) {
		if (count == N) {
			answer++;
			return;
		}
		if (total < left) {
			int num = 1;
			for (int i = 0; i < N - count; i++) {
				num *= 2;
			}
			answer += num;
			return;
		}

		if (left >= right + choosed[count]) {

			check(count + 1, choosed, left, right + choosed[count]);
		}
		check(count + 1, choosed, left + choosed[count], right);

	}
}

두 번째론 모든 순열을 만들지 않고, 순열을 만드는 과정 안에 조건에 따른 검증을 넣어서 가지치기한 코드입니다.

마찬가지로 시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고, (N-현재 단계)! * 2^(N-현재 단계)만큼 더해주었습니다.

순열이 다 만들어지지 않았기 때문에 경우의 수를 계산할 때 남은 추의 개수 팩토리얼까지 곱해주어야 합니다.

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

public class q3234_SWEA_준환이의양팔저울Re {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new boolean[N], 0, 0);

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

		System.out.println(sb);
	}

	static void makePermutation(int count, boolean[] visited, int left, int right) {
		// System.out.println(count + "선택됨," + left + " : " + right);

		if (count == N) {
			answer++;
			return;
		}

		if (total < left) {
			int num = 1;
			for (int i = 1; i <= N - count; i++) {
				num *= 2;
				num *= i;
			}
			answer += num;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				makePermutation(count + 1, visited, left + gram[i], right);
				if (right + gram[i] <= left) {
					makePermutation(count + 1, visited, left, right + gram[i]);
				}
				visited[i] = false;
			}
		}
	}
}

세 번째로 메모이제이션을 활용해서 이미 탐색한 경우를 스킵한 코드입니다.

어떤 방법으로든 추의 위치 배정이 똑같은 시점이 오면 이후의 경우의 수의 개수는 같아집니다.

예를 들어 1,2,8,... 의 무게를 가진 추가 주어졌을때, 8(좌) → 1(우) → 2(우) 경우나 8(좌) → 2(우) → 1(우) 경우나 추의 현재 상태는 같습니다.

추의 상태가 같으면 이후 가능한 경우의 수도 같아집니다.

추의 상태를 사용한 추 (갯수가 작기 때문에 비트 마스킹으로 기록), 좌측에 놓인 무게로 저장하고 이전에 탐색한 적이 있다면 더 탐색을 하지 않고 그 값을 사용하는 코드입니다.

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

public class q3234_SWEA_준환이의양팔저울Re2 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, total;
	static int[] gram;
	static int[][] memo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			total = 0;
			gram = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}

			memo = new int[total + 1][1 << N];

			sb.append("#").append(tc).append(" ").append(makePermutation(0, 0, 0, 0)).append("\n");
		}

		System.out.println(sb);
	}

	static int makePermutation(int count, int bitmask, int left, int right) {
		if (count == N) {
			return 1;
		}

		int sum = memo[left][bitmask];

		if (sum == 0) {
			for (int i = 0; i < N; i++) {
				if ((bitmask & (1 << i)) == 0) {
					sum += makePermutation(count + 1, bitmask | (1 << i), left + gram[i], right);
					if (right + gram[i] <= left) {
						sum += makePermutation(count + 1, bitmask | (1 << i), left, right + gram[i]);
					}
				}
			}
			return memo[left][bitmask] = sum;
		}
		return sum;
	}
}

위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.

여러가지로 생각할 거리가 많은 좋은 문제였습니다.