17182번 - 우주 탐사선
문제 풀이 시간 : 1시간
문제 풀이:
처음에는 그냥 플로이드로 모든 경로의 최단 거리를 구하고
각 위치에서 가지 않은 행성 중 최단 거리인 행성을 골라서 가는 방식으로 문제를 풀었다.
플로이드 함수
public static void update() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i==j)
continue;
for (int k = 0; k < n; k++) {
arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
}최단 거리 계산
Queue<Integer> q = new LinkedList<>();
visited[k] = true;
q.add(k);
int sum = 0;
while (!q.isEmpty()) {
int a = q.poll();
int min = Integer.MAX_VALUE;
int idx = a;
for (int i = 0; i < n; i++) { //현재 행성에서 갈 수 있는 모든 행성 탐색
if (visited[i]||a==i) { //방문했거나 현재 행성과 같다면 패스
continue;
}
if (min > arr[a][i]) { //이동 시간이 더 짧다면 교체
min = arr[a][i];
idx = i;
}
}
if (idx != a) { //현재 행성과 저장된 행성이 같다면 모든 행성을 방문했다는 뜻
sum += min;
visited[idx] = true;
q.add(idx);
}
}근데 이건 아주 잘못된 접근이었다.
제대로된 풀이를 하려면 시작지점에서부터 모든 경우를 계산하면 되는 것이다.
실제로 모든 경우의 수를 다 해보더라도 행성의 개수가 10개이므로 크게 부담되지 않는다.
그래서 위의 코드에서 최단 거리 계산 코드를 아래와 같은 코드로 바꿔주면 된다.
public static void calc(int cnt, int a, int sum) { //행성 방문 개수, 현재 행성, 거리 합계
if (ans < sum) { //이미 최단값보다 크다면 할필요 없음
return;
}
if (cnt >= n) { //모든 행성을 방문했다면 최단값 업데이트
ans = sum;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i] || a == i) {
continue;
}
visited[i] = true;
calc(cnt + 1, i, sum + arr[a][i]); //재귀
visited[i] = false;
}
}전체 코드
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 Main {
public static int n,k;
public static int ans = Integer.MAX_VALUE;
public static int[][] arr;
public static boolean[] visited;
public static void calc(int cnt, int a, int sum) {
if (ans < sum) {
return;
}
if (cnt >= n) {
ans = sum;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i] || a == i) {
continue;
}
visited[i] = true;
calc(cnt + 1, i, sum + arr[a][i]);
visited[i] = false;
}
}
public static void update() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i==j)
continue;
for (int k = 0; k < n; k++) {
arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
update();
visited[k] = true;
calc(1, k, 0);
System.out.println(ans);
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.