글 읽기 - 1719 택배 문제 반례가 뭘까요? ㅠ

wagurano 4년 전 1

이전 정보까지 구하는것 까지 했는데요.

dfs로 output 테이블을 만들었는데 제출하면 15프로에서 멈춥니다.

물론 다른방법으로 풀긴했는데, makeTable에서 뭘 틀렸을까요?

매우 찜찜해서요 ㅠ

고수님들 도와주시면 감사하겠습니다 ㅠ

잠이안오네요ㅠ

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

public class Main {

	static int[] visit, D, path;
	static int N,M;
	static ArrayList[] input;
	static int[][] out;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		N = Integer.parseInt(token.nextToken().toString().trim());
		M = Integer.parseInt(token.nextToken().toString().trim());
		
		input = new ArrayList[N+1];
		for(int i = 1 ; i<=N ; i++) input[i] = new ArrayList<>();
		
		for(int i = 1 ; i<=M ; i++) {
			token = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(token.nextToken().toString().trim());
			int b = Integer.parseInt(token.nextToken().toString().trim());
			int c = Integer.parseInt(token.nextToken().toString().trim());
			input[a].add(new Pair(b, c));
			input[b].add(new Pair(a, c));
		}
		
		out = new int[N+1][N+1];
		
		for(int i = 1 ; i<=N ; i++) {
			diik(i);
		}
		for(int i = 1 ; i<=N ; i++) {
			for(int j = 1 ; j<=N ; j++) {
				if(i == j) {
					System.out.print('-'+" ");
				}else if(out[i][j]==-1){
					System.out.print('0'+" ");
				}else {
					System.out.print(out[i][j]+" ");
				}
			}
			System.out.println("");
		}
		
	}

	private static void diik(int i) {
		visit = new int[N+1];		
		path = new int[N+1];
		Arrays.fill(path, -1);
		path[i]=0;
		D = new int[N+1];
		Arrays.fill(D, Integer.MAX_VALUE);
		
		PriorityQueue<Pair> que = new PriorityQueue<Pair>(new Comparator<Pair>() {
			@Override
			public int compare(Pair o1, Pair o2) {
				return o1.wgt - o2.wgt;
			}
		});
		que.add(new Pair(i, 0));
		while(!que.isEmpty()) {
			Pair now = que.poll();
			int start = now.next;
			if(visit[start]==1)continue;
			visit[start]=1;
			
			ArrayList nextList = input[start];
			for(int n = 0 ; n<nextList.size() ; n++) {
				Pair next = (Pair) nextList.get(n);
				int end = next.next;
				if(visit[end] == 0) {
					if(D[end] > D[start]+next.wgt) {
						D[end] = D[start]+next.wgt;
						que.add(new Pair(end, D[end]));
						path[end] = start;//path만들기
					}
				}
				
			}	
		}
		
		//table 만들기
		makeTable(path, i, 1);
	}

	private static void makeTable(int[] path, int i, int n) {
		for(int j = 1 ; j<=N ; j++) {
			
				if(path[j] == i){
					out[i][j] = j;
					n = j;
					makeTables(path, i, n, n);
				}
			
		}		
	}

	private static void makeTables(int[] path, int i, int n, int m) {
		for(int j = 1 ; j<=N ; j++) {
			
				if(path[j] == m){
					out[i][j] = n;
					m = j;
					makeTables(path, i, n, m);
				}
			
		}
	}
}


class Pair{
	int next, wgt;

	public Pair(int next, int wgt) {
		super();
		this.next = next;
		this.wgt = wgt;
	}
	
}

wagurano 4년 전 0

자답씁니다.

재귀로 호출할때 m =j 부분때문에 뒷부분이 적용이 안되는 현상이 생기네요

m은 변경하면 안되고

out[i][j] = n;
//m = j;
makeTables(path, i, n, j);

그냥 이렇게 처리하니 됩니다....아주 초보적인 실수를....재귀 조심해야겠네요 ㅠ

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

문제

문제

출처

ICPC

1719 택배 문제 반례가 뭘까요? ㅠ

wagurano 4년 전 1

wagurano 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말