글 읽기 - 문제를 풀었으나 이해가지 않는 부분이 있어 질문 올립니다.

patabear 3년 전 0

BFS를 이용하여 문제를 풀었습니다. 반례를 찾고싶어 질문 올립니다.

제출번호 : 27358422 에서는 queue에 출발지 X로부터 1만큼 거리가 있는 정점들의 값과

거리 1의 값을 주고 queue에 추가하여 그 아래에 있는 while문을 통과하여 거리 K값인 경우 답을 찾는 방식으로 진행했지만

틀렸습니다가 떴습니다.

제출번호 : 27358441 에서는 queue에 출발지 X의 값과 거리 0을 주고 위와 같은 방식으로 진행하였는데

맞았습니다가 떴습니다.

위와 같은 차이가 나려면 K = 0 인 테스트케이스가 있다고 생각하는데

문제에서 K의 값은 (1 <= K <= 300000) 이어서 K = 0인 경우가 아닌 다른 경우에서 위의 차이가 나는 것인지

아니면 문제의 K값이 정말 0인 테스트케이스가 있는지 잘 모르겠습니다.

만약 테스트케이스에 K=0인 경우가 없다면 위의 두가지에서 어떠한 차이가 발생하는지 궁금합니다.

답변해주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int K;
	static int X;
	static Queue<struct> queue;
	static HashMap<Integer, ArrayList<Integer>> hashMap;
	static boolean[] visited;
	static ArrayList<Integer> answer;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		queue = new LinkedList<struct>();
		hashMap = new HashMap<>();
		visited = new boolean[N+1];
		answer = new ArrayList<>();
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			if(hashMap.containsKey(from)) {
				hashMap.get(from).add(to);
			}
			else {
				ArrayList<Integer> temp_arr = new ArrayList<>();
				temp_arr.add(to);
				hashMap.put(from, temp_arr);
			}
		}
		
		if(!hashMap.containsKey(X)) {
			System.out.println("-1");
			return;
		}
		
		visited[X] = true;
		
		// 아래의 코드가 다른점입니다.
		//----------------------------
		
		// 1번 : 이  주석처리된 부분을 사용하면 틀렸습니다가 나옵니다.
//		for(int x: hashMap.get(X)) {
//			queue.add(new struct(x, 1));
//			visited[x] = true;
//		}
		
		// 2번 : 아래 이 한줄을 사용하면 맞았습니다가 나옵니다.
		queue.add(new struct(X, 0));
		
		//----------------------------
		
		while(!queue.isEmpty()) {
			struct str = queue.poll();
			if(str.depth > K) break;
			
			if(str.depth == K) {
				answer.add(str.val);
				continue;
			}
			
			if(hashMap.containsKey(str.val)) {
				ArrayList<Integer> temp_arr = hashMap.get(str.val);
				for(int x: temp_arr) {
					if(!visited[x]) {
						visited[x] = true;
						queue.add(new struct(x, str.depth+1));
					}
				}
			}
		}
		
		if(answer.size() == 0) {
			System.out.println("-1");
		}
		
		else {
			Collections.sort(answer);
			
			for(int x: answer) {
				System.out.println(x);
			}
		}
	}
	
	static class struct {
		public struct(int val, int depth) {
			this.val = val;
			this.depth = depth;
		}
		int val;
		int depth;
	}

}

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