1. 문제
https://www.acmicpc.net/problem/10971
2. 풀이과정
1) 시작점 = 출발점이므로, 출발점은 어디든 결과는 같다. 따라서 시작점은 0으로 고정했다.
2) 순서에 따라 결과가 달라지는 순열 문제이다. 그리고 마지막에 도착지 => 출발지까지 값도 고려해주는 걸 잊지말자.
import java.io.*;
import java.util.*;
public class Boj10971 {
static int N, cost[][], result;
public static void dfs(int x, int cnt, int sum, int visited) {
if(cnt==N) {
result = Math.min(result, sum+cost[x][0]);
return;
}
for(int i=1; i<N; i++) {
if((visited&(1<<i))==0) {
dfs(i, cnt+1, sum+cost[x][i], visited|(1<<i));
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
cost = new int[N][N];
final int INF = 999_999_999;
result = INF;
StringTokenizer st = null;
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
cost[i][j] = Integer.parseInt(st.nextToken());
cost[i][j] = (cost[i][j]==0) ? INF : cost[i][j];
}
}
dfs(0, 1, 0, 1<<0);
System.out.println(result);
}
}
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 2056번 : 작업* (0) | 2022.07.01 |
---|---|
[Java] 백준 1941번 : 소문난 칠공주* (0) | 2022.06.30 |
[Java] 백준 1799번 : 비숍 (0) | 2022.06.20 |
[Java] 백준 3954번 : Brainf**k 인터프리터 (0) | 2022.06.16 |
[Java] 백준 17472번 : 다리 만들기 2 (0) | 2022.06.05 |