글 읽기 - 반례 찾아주실 분 구합니다(3% 에서 실패)

himinhee 1년 전 0

질문하기에 나와있는 반례들도 넣어서 실행시켜 보았는데 잘 나옵니다ㅠㅠ

제가 어떤 것을 놓치고 있는걸까요?.....

반례 찾아주시는 분은 복받으실꺼에요

import java.util.Scanner;
import java.util.Stack;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), M = sc.nextInt(), R = sc.nextInt();
		
		// 그래프 구현 
		HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
		for (int i = 0; i < M; i++) {
			int n1 = sc.nextInt(), n2 = sc.nextInt();
			
			if (graph.get(n1) == null) graph.put(n1, new ArrayList<Integer>());
			graph.get(n1).add(n2);
			
			if (graph.get(n2) == null) graph.put(n2, new ArrayList<Integer>());
			graph.get(n2).add(n1);
		}
		
		// 인접 노드 오름차순으로 방문 하기 위해 연결되어 있는 노드들을 내림차순으로 정렬 
		for (ArrayList<Integer> val: graph.values()) Collections.sort(val, Collections.reverseOrder());
		
		
		// dfs   
		boolean[] visited = new boolean[N + 1];
		int[] order = new int[N + 1];            // 방문순서 기록할 배열 선언 
		int cnt = 0;                             // 방문순서 count할 변수 선언 
		
		Stack<Integer> stack = new Stack<>();
		stack.push(R);
		visited[R] = true;
		
		while (!stack.empty()) {
			int n = stack.pop();
			cnt++;
			order[n] = cnt;
			
			if (graph.get(n) == null) continue;
			
			for (int i = 0; i < graph.get(n).size(); i++) {
				if (!visited[graph.get(n).get(i)]) {
					stack.push(graph.get(n).get(i));
					visited[graph.get(n).get(i)] = true;
				}
			}
		}
		
		// 정답 출력 
		for(int i = 1; i < order.length; i++) System.out.println(order[i]);

	}

}

stylecoke 1년 전 2

예를 들어, 입력이 아래와 같이 주어진다고 가정하면

4 4 1
1 2
1 3
1 4
2 4

방문 순서는 1 -> 2 -> 4 -> 3가 되어야 하지만

질문자님의 코드는 stack에 push하면서 visit여부를 체크하므로 마치 bfs를 하듯이 1 -> 2 -> 3 -> 4 순서로 방문하게 됩니다.

(p.s 생각보다 반례 찾기 힘드네요 ㅎㅎ..)

stylecoke 1년 전 2

좀 더 자세히 질문자님의 코드가 동작하는 방식을 설명하면 아래와 같습니다.

1. 1을 방문하면서 2, 3, 4를 stack에 push후 visited을 true로 바꿈

2. 2을 방문후 4를 방문해야 하는데 이미 1에서 4를 visited = true로 하였으므로 skip

3. 3을 방문

4. 4을 방문

himinhee 1년 전 0

stylecoke 님의 자세한 설명과 입력받는 방식 바꿔서(시간초과때문에ㅠㅠ) 해결했습니다 감사합니다!!ㅎㅎ

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

문제

문제

출처

ICPC

반례 찾아주실 분 구합니다(3% 에서 실패)

himinhee 1년 전 0

stylecoke 1년 전 2

stylecoke 1년 전 2

himinhee 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말