오답노트 #10971 : 외판원 순회 2

풀이방법 및 문제점

2022.11.23

이번 문제도 작은 실수로 인해 틀렸던 문제이다.

백트래킹 문제를 풀 때 절대 잊으면 안 되는 부분이기 때문에 오답노트에 적어두려 한다.

 

재귀를 통해 각 도시를 방문하다가,

모든 도시를 빠짐없이 방문한 것이 확인되면 출발지로 다시 돌아가는 비용을 현재까지 쌓인 비용에 더한 뒤 이번 여정의 최종 비용으로 결정하기로 하였다.

단, 마지막으로 방문한 도시에서 출발지로 돌아가는 길이 없다면 이번 여정은 무효로 처리하고 정답에 반영하지 않는다.

 

그 다음 모든 최종 비용 값 중 최솟값을 화면에 출력하여 문제를 해결한다.

 

이러한 풀이 방식은 잘 짠 것이었다.

 

단, 백트래킹 문제를 풀 때 꼭 기억해야 하는 사항 하나를 깜빡하여 틀렸었다.

백트래킹이란, 갔던 길을 되돌아오기를 반복하며 최적의 값을 찾아나가는 알고리즘이다.

그러므로 갔던 길을 되돌아오기, 즉 그 길을 가기 위해 수행했던 계산을 다시 없던 것으로 되돌리는 작업이 빈번히 일어난다.

이번 문제에서는 각 도시를 방문했는지 여부를 저장하는 visited 배열을 사용하였는데, c번 도시를 방문했다면 visited[c] == true 이고 그렇지 않다면 visited[c] == false 인 식이다.

각 도시에 처음 발을 들일 때에는 visited 값이 true로 바뀐다.

그러나 백트래킹이 일어날 때마다, 즉 각 도시에서 하는 작업이 끝나서 return을 해야 할 때마다 그 전에 visited 배열의 값을 다시 false로 되돌려주어야 한다. 그 도시를 방문한 적 없는 것처럼 되돌려놓아야 한다.

모든 분기에서 이 작업을 하도록 빠짐없이 설정한 줄 알았는데, 실수로 딱 하나의 분기에서 visited[cur] = false; 를 빼먹었다.

그래서 백트래킹을 한 뒤에도 그 도시는 이미 방문한 것으로 표시되어있었고 이 때문에 정답보다 적은 결과값이 도출되어 틀리고 말았다.

 

백트래킹 문제를 풀 때에는

모든 데이터가 이전의 상태로 완벽하게 되돌아가고 있는지 철저하게 확인하자!

 

정답 게시글 바로가기

 

 

코드

Java(2022.11.23) (visited[cur] = false 한 줄이 빠져 틀린 코드)

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

public class Main {
	
	static int n;	//도시의 수
	static boolean[] visited;	//방문 여부 기록용 배열
	static ArrayList<ArrayList<Integer>> info = new ArrayList<ArrayList<Integer>>();
	static int answer;	//정답을 저장할 변수

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/*
		 * 입력값 받아오기
		 */
		n = Integer.parseInt(br.readLine());
		
		visited = new boolean[n];
		for(int i=0; i<n; i++) info.add(new ArrayList<Integer>());
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++)
				info.get(i).add(Integer.parseInt(st.nextToken()));
		}
		
		
		/*
		 * 문제 해결
		 */
		
		answer = Integer.MAX_VALUE;
		
		for(int i=0; i<n; i++) {
			Arrays.fill(visited, false);
			visited[i] = true;
			for(int j=0; j<n; j++) {
				int cost = info.get(i).get(j);
				if(cost == 0) continue;	//갈 수 없는 도시이면 무시
				solve(i, j, cost);
			}
		}
		
		
		/*
		 * 정답 출력
		 */
		System.out.print(answer);
		

	}
	
	//재귀적으로 정의된 문제해결 함수
	//매개변수는 출발한 첫 도시(start), 현재 있는 도시(cur), 현재까지 든 비용(sum)
	public static void solve(int start, int cur, int sum) {
		//이미 방문한 도시인 경우 리턴
		if (visited[cur]) return;

		
		//처음 온 도시인 경우
		//이 도시에 새로 방문했음을 표시
		visited[cur] = true;
			
		
		//이번 도시에 옴으로써 모든 도시를 다 방문한 경우
		//첫 도시로 돌아가는 비용을 더하여 최종 계산을 한 후 리턴
		if(allTrue()) {
			//만약 현재 도시에서 출발지점으로 돌아가는 길이 없는 경우 그냥 리턴
			if(info.get(cur).get(start) == 0) {
				visited[cur] = false;
				return;
			}
			//그렇지 않은 경우엔 최종 계산 수행
			sum += info.get(cur).get(start);
			answer = Math.min(answer, sum);
			//visited[cur] = false; !!!!이 코드를 빼먹어 틀렸었다!!!!
			return;
		}
		
		
		//아직 갈 도시가 더 남은 경우
		//이 도시에서부터 길이 뻗어있는 모든 도시에 대하여 재귀
		for(int i=0; i<n; i++) {
			int cost = info.get(cur).get(i);
			if (cost == 0) continue;	//갈 수 없는 도시이면 무시
			solve(start, i, sum + cost);
		}
		
		visited[cur] = false;
		return;
		
	}
	
	//모든 도시를 다 방문했는지 체크하는 함수
	//아직 안 간 도시가 하나라도 있으면 false를 리턴, 모든 도시를 갔으면 true를 리턴
	public static boolean allTrue() {
		for(boolean b: visited) {
			if(!b) return false;
		}
		return true;
	}

}