[백준/java] 10971. 외판원 순회 2

문제 링크 - https://www.acmicpc.net/problem/10971

🌱 문제

🌱 풀이

생각한 풀이 방식은 2차원 배열 혹은 2차원리스트에 간선정보(비용 정보)를 저장한다음, 모든 정점을 시작정점으로 해서 DFS를 돈 후 전체 정점갯수만큼 돌았을때의 최솟값을 구하는 방식이다.

• 간선리스트와 비용 배열
  인접 정점을 간선리스트에 저장하고, 비용정보를 2차원 배열 dist[][]에 저장했다.
  하지만 풀고나서 생각해보니 dist[][]가 0인지 0이아닌지로 연결되어있는지 확인할 수 있으므로 간선리스트는 굳이 필요가 없었다.

for (int i = 0; i < n; i++) {
			edges[i] = new ArrayList<Integer>();
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());
				if (x != 0) {
					edges[i].add(j);
					dist[i][j] = x;
				}
			}
		}

• 모든 정점에서 dfs 실행하기

for (int i = 0; i < n; i++) {
			visited = new boolean[n];
			cnt = 0;
			sum = 0;
			visited[i]=true;
			dfs(i, i, cnt, sum);
}

• dfs
  방문체크를 해주면서 dfs를 돈다. 매개변수로 (int start, int v, int cnt, int sum) = (시작 정점, 현재 정점,현재까지 거쳐온 정점 갯수, 현재까지의 비용 합)을 넘겨준다.
  이때 주의할점은 sum+=dist[v][next]; 를 실행하고나서 sum을 넘겨주면 안되고, 저장하지 않아야 하므로 sum+dist[v][next] 자체를 다음 dfs로 넘겨줘야 한다.

public static void dfs(int start, int v, int cnt, int sum) {
		if (cnt == n-1) { //n개 연결되었으면 마지막정점과 첫 정점 연결되었는지 확인하고 answer 갱신하기 
			if (dist[v][start] != 0)
				answer = Math.min(answer, sum+dist[v][start]);
			return;

		}
		int cur = v;
	
		for (int i = 0; i < edges[v].size(); i++) {
			int next = edges[v].get(i);
			if (visited[next] == false) {
				visited[v] = true;
				dfs(start,next, cnt + 1, sum + dist[v][next]);
				visited[next] = false;
			}
		}
	}

🌱 코드

package Sep_week03;

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

public class boj_10971 {
	static int n;
	static int cnt, sum, last;
	static int answer = Integer.MAX_VALUE;
	static boolean[] visited;
	static ArrayList<Integer> edges[]; //간선 리스트 
	static int[][] dist;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		edges = new ArrayList[n];
		dist = new int[n][n];

		for (int i = 0; i < n; i++) {
			edges[i] = new ArrayList<Integer>();
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());
				if (x != 0) {
					edges[i].add(j);
					dist[i][j] = x;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			visited = new boolean[n];
			cnt = 0;
			sum = 0;
			visited[i]=true;
			dfs(i, i, cnt, sum);
		}
		System.out.println(answer);
	}

	public static void dfs(int start, int v, int cnt, int sum) {
		if (cnt == n-1) {
			if (dist[v][start] != 0)
				answer = Math.min(answer, sum+dist[v][start]);
			return;

		}
		int cur = v;
	
		for (int i = 0; i < edges[v].size(); i++) {
			int next = edges[v].get(i);
			if (visited[next] == false) {
				visited[v] = true;
				dfs(start,next, cnt + 1, sum + dist[v][next]);
				visited[next] = false;
			}
		}
	}

}