백준 17182번: 우주 탐사선

문제 설명

• https://www.acmicpc.net/problem/17182

접근법

• 못풀었습니다. 어떤 개념을 어떻게 사용해야 할지에 대한 이해가 많이 부족했습니다.

처음 생각한 틀린 풀이 일부

	public static void DFS(int depth, int from, int score, int status, int N, int[][] board, boolean[][][] v) {
		if(status == ((int)Math.pow(2, N)-1)) {
			minVal = Math.min(minVal, score);
			return;
		}
		for (int to = 0; to < N; to++) {
			if(from == to) continue;
			if(v[from][to][status]) continue;
			v[from][to][status] = true;
			int nextStatus = (status | 1<<to);
			int nextScore = score + board[from][to];
			DFS(depth+1,to,nextScore,nextStatus,N,board,v);
			v[from][to][status] = false;
			
		}
	}

또다른 틀린 풀이

	public static void BFS(int N, int start,int[][] board) {
		boolean[][][] v = new boolean[N][N][(int)Math.pow(2, N)];
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {start,0,1<<start});
		while(!q.isEmpty()) {
			int[] now = q.poll();
			for (int to = 0; to < N; to++) {
				if(now[0] == to) continue;
				if(v[now[0]][to][now[2]]) continue;
				v[now[0]][to][now[2]] = true;
				int keySet = (now[2] | 1<<to);
				if(now[2] == 0) {
					q.add(new int[] {to,now[1]+board[now[0]][to],keySet});
				}else {
					q.add(new int[] {to,now[1]+board[now[0]][to],now[2]});
				}
			}
		}
	}

이 경우 다른 이동이 같은 방문배열을 공유한다는 문제가 발생합니다.

• 1->3->0과 1->0->3->0은 모두 숫자 0,1,3을 가져 keySet이 11입니다.
• 빨간색이 먼저 실행된다 가정하면 keySet이 11일때의 방문배열의 0번 노드를 방문처리 됩니다.
• 이후 파란색이 방문하면 keySet이 11일때 0번 노드를 방문하지 않았지만 빨간색 때문에 방문한 것으로 처리됩니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int minVal = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int k = 0; k < board.length; k++) {
			for (int i = 0; i < board.length; i++) {
				for (int j = 0; j < board.length; j++) {
					board[i][j] = Math.min(board[i][j], board[i][k] + board[k][j]);
				}
			}
		}

		
		boolean[] v = new boolean[N];
		v[K] = true;
		DFS(0,0,K,N,v,board);
		System.out.println(minVal);
	}
	
	public static void DFS(int depth, int score, int now, int N, boolean[] v, int[][] board) {
		if(depth ==N-1) {
			minVal = Math.min(minVal, score);
			return;
		}
		for (int i = 0; i < N; i++) {
			if(v[i]) continue;
			v[i] = true;
			DFS(depth+1,score+board[now][i],i,N,v,board);
			v[i] = false;
		}
	}
	
	public static void BFS(int N, int start,int[][] board) {
		boolean[][][] v = new boolean[N][N][(int)Math.pow(2, N)];
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {start,0,1<<start});
		while(!q.isEmpty()) {
			int[] now = q.poll();
			for (int to = 0; to < N; to++) {
				if(now[0] == to) continue;
				if(v[now[0]][to][now[2]]) continue;
				v[now[0]][to][now[2]] = true;
				int keySet = (now[2] | 1<<to);
				if(now[2] == 0) {
					q.add(new int[] {to,now[1]+board[now[0]][to],keySet});
				}else {
					q.add(new int[] {to,now[1]+board[now[0]][to],now[2]});
				}
			}
		}
	}
	
	
}
/*
10 0
0 1 1 1 1 1 1 1 1 1 
1 0 1 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 1 0 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 0 1 1 1 1 
1 1 1 1 1 1 0 1 1 1 
1 1 1 1 1 1 1 0 1 1 
1 1 1 1 1 1 1 1 0 1 
1 1 1 1 1 1 1 1 1 0 
*/