백준_10971_외판원순회2

https://www.acmicpc.net/problem/10971

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

public class Main {
	static int N;
	static int[][] W;
	static boolean[] visited;
	static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		W = new int[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				W[i][j] = Integer.parseInt(st.nextToken());
			}
		}

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

		System.out.println(ans);
	}

	static void dfs(int start, int cur, int cnt, int cost) {
		if (cnt == N) {
			if (W[cur][start] != 0) {
				ans = Math.min(ans, cost + W[cur][start]);
			}
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i] && W[cur][i] != 0) {
				visited[i] = true;
				dfs(start, i, cnt + 1, cost + W[cur][i]);
				visited[i] = false;
			}
		}
	}

}

• 시작점에 따라 DFS 탐색 시작
• cnt값을 줘서 간단하게 전부 탐색했는지 확인 가능!
• 순열과 비슷!

📌 마지막 조건 주의!

		if(cnt == N){
            ans = Math.min(ans, cost + W[cur][start]);
            return;
        }

• 이렇게 하면 마지막 종착지에서 출발점으로 돌아가는 것을 고려하지 않게됨!

		if (cnt == N) {
            if(W[cur][start] != 0){
                ans = Math.min(ans, cost + W[cur][start]);
            }
            return;
        }

• 출발점으로 돌아갈 수 있는지 여부를 확인하고 추가로 cost를 더해줘야함!

2차원 배열 찍어보기

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

for (int[] row : map) {
	System.out.println(Arrays.toString(row));
    }

Arrays.stream(map)
              .map(row -> Arrays.toString(row))
              .forEach(System.out::println);