728x90
[백준] 10971번 - 외판원 순회 2 (!) (JAVA)
[ 접근 방법 ]
DFS를 이용하여 해결하였다.
* 첫번째 방법 (시간초과)
첫번째로 생각한 방법은 N X N 비용 2차원 배열에, 각 행과 열에 중복하지 않고, N개의 원소를 선택하는 방법이다.
* 문제에 예제 1을 그래도 사용하였다.
경로 : 2 -> 1
row : 2 와 col : 1 을 제외한다.
경로 : 2 -> 1 -> 3
row : 1 와 col : 3 을 제외한다.
경로 : 2 -> 1 -> 3 -> 4
row : 3 와 col : 4 을 제외한다.
경로 : 2 -> 1 -> 3 -> 4 -> 2
row : 4 와 col : 2 을 제외한다.
* 두번째 방법 (성공)
DFS 함수에 매개변수로,
경로의 출발위치는 나타내는 "start"
현재위치를 나타내는 "now"
지난 도시의 수를 나타내는 "depth"
경로의 누적 비용을 나타내는 "sum"
을 사용한다.
void dfs(int start, int now, int depth, int sum){
// 현재 위치 == 시작점 AND 경로 누적 비용 > 0
if(now == start AND sum > 0){
최솟값 갱신 (현재 누적 비용, 최솟값)
return;
}
for(i : 1 -> N){
if(길이 존재 O){
// 모든 도시를 방문한 경우에 시작 위치로 이동가능
if(i == start AND depth == N){
sum += (now -> i 이동 비용)
dfs(start, i, depth + 1, sum)
}
else if(i에 방문하지 않음){
i에 방문함을 저장.
sum += (now -> i 이동 비용)
dfs(start, i, depth + 1, sum)
// 복원
sum -= (now -> i 이동 비용)
i에 방문하지 않음을 저장.
}
}
}
return;
}
* 모든 도시를 다 방문한 다음에 시작도시로 이동할 수 있도록 별도 예외 처리
[ JAVA 코드 - 첫번째 방법 (시간 초과) ]
// 10971번 - 외판원 순회 2
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[][] cost; // 경로 별 비용
static int[] arr; // 비용 배열
static boolean[] visit_row; // 행 방문 여부
static boolean[] visit_col; // 열 방문 여부
static int min = Integer.MAX_VALUE; // 최소 비용
// 최소 비용 찾기
public static void findMin(int depth){
// 모든 경로 탐색
if(depth == N){
int sum = 0;
for(int val : arr){
sum += val;
}
min = Math.min(min, sum);
return;
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
// 탐색하지 않은 행/열 AND 길이 존재하면 탐색
if(!visit_row[i] && !visit_col[j] && cost[i][j] != 0){
visit_row[i] = true;
visit_col[j] = true;
arr[depth] = cost[i][j];
findMin(depth + 1);
visit_row[i] = false;
visit_col[j] = false;
}
}
}
return;
}
public static void main(String[] args) throws IOException {
// 0. 입출력 선언 / 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
cost = new int[N][N];
arr = new int[N];
visit_row = new boolean[N];
visit_col = new boolean[N];
for(int i=0; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1. 최소 비용 구하기
findMin(0);
// 2. 최소 비용 출력
bw.write(min + "\n");
bw.flush();
br.close();
bw.close();
}
}
[ JAVA 코드 - 두번째 방법 (성공) ]
// 10971번 - 외판원 순회 2
import java.util.*;
import java.io.*;
public class Main {
static int min = Integer.MAX_VALUE;
static int[][] cost;
static int N;
static boolean[] visit;
static int[] arr;
public static void dfs(int start, int now, int depth, int sum){
if(now == start && sum > 0){
min = Math.min(min, sum);
return;
}
for(int i=1; i<=N; i++){
if(cost[now][i] > 0){
if(i == start && depth == N){
sum += cost[now][i];
dfs(start, i, depth + 1, sum);
}
else if(!visit[i]) {
visit[i] = true;
sum += cost[now][i];
dfs(start, i, depth + 1, sum);
sum -= cost[now][i];
visit[i] = false;
}
}
}
return;
}
public static void main(String[] args) throws IOException {
// 0. 입출력 선언 / 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
cost = new int[N+1][N+1];
visit = new boolean[N+1];
for(int i=1; i<=N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++){
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
visit[1] = true;
dfs(1, 1, 1, 0);
bw.write(min + "\n");
bw.flush();
br.close();
bw.close();
}
}[Rewind]
1. 어려웠던 점
- 경로 끝에 출발했던 도시로 돌아오는 것을 따로 예외처리 하는 것이 어려웠다.
2. 알게된 점
- DFS 문제를 조금만 틀면 풀이방법을 생각하기에 매우 까다로움.
- DFS 함수에 매개변수를 좀더 적극적으로 활용해야 함.
3. 개선 방향
- 응용 문제를 반복하여 풀어서 숙달해야 함.
728x90
