글 읽기 - (스포) 왜 맞았는지 모르겠습니다.

gpejvkdlf17 1년 전 0

DFS로 풀었습니다.

27번 라인의 반복문 내부에서

출발 지점을 방문처리 한 뒤

방문 비용 계산이 종료된 후에 다시 방문 처리를 초기화 시켜주어야 하지 않나요?

실수로 방문 처리 초기화를 시키지 않은 아래 코드를 올렸는데 맞았습니다가 나옵니다.

문제가 잘못되었을 것 같지는 않은데,

왜 아래 코드가 정답처리 되는지 궁금합니다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N;
	static int[][] map;
	static boolean[] visit;
	static int min;
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new boolean[N];
		
		for(int i = 0; i < map.length; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < map[i].length; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		min = Integer.MAX_VALUE;
		for(int i = 0; i < N; i++) {
			visit[i] = true;
			sol(i, i, 1, 0);
		}
		bw.write(min+"");
        bw.flush();
        bw.close();
        br.close();
    }
	
	public static void sol(int first, int start, int depth, int sum) {
		if(depth==N) {
			if(map[start][first]==0) return;
			sum += map[start][first];
			min = Math.min(min, sum);
			return;
		}
		for(int j = 0; j < map[0].length; j++) {
			if(visit[j] || map[start][j]==0) continue;
			visit[j] = true;
			sol(first, j, depth+1, sum+map[start][j]);
			visit[j] = false;
		}
	}
		
}

byeongkeunahn 1년 전 0

TSP는 모든 정점이 포함되는 경로를 찾는 것이기 때문에 가장 처음으로 고려하는 정점이 1에서 N까지 중 어느 것이어도 상관이 없습니다. 따라서 루프의 첫 실행 시 정답이 계산됩니다. 두 번째부터는 정점이 하나 이상 부족하기 때문에 36번 줄의 조건을 만족시키는 경우가 없어 min이 갱신되지 않습니다. 따라서 실행 후 min에는 정답이 들어있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(스포) 왜 맞았는지 모르겠습니다.

gpejvkdlf17 1년 전 0

byeongkeunahn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말