글 읽기 - 예외케이스 좀 알려주세요

citizen 7년 전 0

혼자 직접 이경우 저경우 다 테스트 해봤는데도 틀린경우를 찾지 못했네요.

일단 저는 팀이 있는 학생들의 수를 구하고

전체 학생수에서 구한 값을 빼 주는 방식으로 문제를 접근하였습니다.

Chain함수에서 arr값을 -1로 만드는 것은 해당 학생번호는 이미

들렀기 때문에 다시 방문할 필요가 없다는 것을 표시하기 위한 것입니다.

Chain을 돌다가 arr값(next)이 start(제일 처음 Chain이 시작된 학생번호)와

일치하면 Chain을 멈추고 학생수들을 더합니다. 그 외에 next가 이미 방문한

학생번호라던지(next = -1인 상황) next가 자기자신의 번호와 일치한다면(Chain을 돌고 있는 경우만)

해당 Chain은 잘못된 것이므로 return해버리구요. 그 외에 상황이라면 next를 이용해

다시 Chain을 돌리도록 하였습니다.

import java.util.*;
import java.awt.List;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int start;
    public static int HasTeam;
    public static int[] arr;
    
    public static void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < t; i++){
        	int n = Integer.parseInt(br.readLine());
        	arr = new int[n+1];
        	st = new StringTokenizer(br.readLine(), " ");
        	for(int j = 1; j <= n; j++){
        		arr[j] = Integer.parseInt(st.nextToken());
        	}
        	HasTeam = 0;
        	for(int j = 1; j <= n; j++){
        		start = j;
        		chain(j, 1);
        	}
        	bw.write((n-HasTeam)+"\n");
        }
        bw.close();
    }
    public static void chain(int place, int size) {
    	if(size == 1){
    		if(arr[place] == -1) return;
    		else if(arr[place] == place) {
    			arr[place] = -1;
    			HasTeam++;
    		} else {
    			int next = arr[place];
    			arr[place] = -1;
    			chain(next, size+1);
    		}
    	}else{
    		int next = arr[place];
    		if(next == start) {
    			HasTeam += size;
    			arr[place] = -1;
    		}else if(next == -1) return;
    		else if(next == place) return;
    		else {
    			arr[place] = -1;
    			chain(next, size+1);
    		}
    	}
    }
}

zlzmsrhak 7년 전 0

반례입니다.

1
3
2 3 2

citizen 7년 전 0

흠.. 제 경우에는

1번 학생이 1->2->3->2로 사이클이 돌기 때문에 1,2,3번 학생 모두를 제외하도록 하였군요.

옳은 방법은 1번만 제외하고 2번학생은 2->3->2로 사이클을 돌아야 하니 답은 1이 되는 건가요?

zlzmsrhak 7년 전 1

답은 1이 맞습니다만, 옳은 방법이라면 1->2->3->2에서 2->3->2 부분의 사이클을 찾아내야 O(N)에 답을 찾을 수 있습니다.

citizen 7년 전 0

마지막 조언을 못 봤더라면 한번 더 틀릴뻔했네요..

도움주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

예외케이스 좀 알려주세요

citizen 7년 전 0

zlzmsrhak 7년 전 0

citizen 7년 전 0

zlzmsrhak 7년 전 1

citizen 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말