글 읽기 - 반례 질문드려요 (+지금까지 나온 반례 정리)

kku64r 1년 전 5

친구가 한 명 밖에 없을 시, 그 친구를 얼리어답터로 설정하고 관계를 끊는 식으로 구현했습니다.

현재 질문 글에 나온 반례들은 전부 정답인데 4%에서 틀렸다고 계속 나옵니다. 새로운 반례 질문드립니다.

그리고 현재까지 나온 반례들 정리해서 공유해드립니다.

```

16
1 2
1 3
1 4
1 5
1 6
2 7
3 8
4 9
5 10
8 11
9 12
9 13
9 14
9 15
9 16
>>5

8
1 2
1 3
1 4
2 5
2 6
4 7
4 8
>>3

9
1 2
1 3
2 4
3 5
3 6
4 7
4 8
4 9
>>3

10
1 2
2 3
2 4
4 6
4 5
6 7
6 8
8 9
8 10
>>4

6
1 2
2 3
2 4
4 5
4 6
>>2

11
1 2
2 3
2 4
2 5
3 6
6 7
4 8
4 9
5 10
1 11
>>5

5
1 5
2 5
3 5
4 5
>>1

9
1 2
2 3
3 4
4 5
2 6
6 7
7 8
1 9
>>4

5
1 2
2 3
3 4
4 5
>>2

```

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static List<Integer>[] list; //친구들 list
	static boolean[] visited; //방문처리
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		//입력
		N = Integer.parseInt(br.readLine());
		list = new ArrayList[N+1];
		for(int i=0; i<=N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		visited = new boolean[N+1];
		
		for(int i=0; i<N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			list[num1].add(num2);
			list[num2].add(num1);
		}
		
		//실행
		for(int i=N; i>0; i--) {
			if(list[i].size() == 1) run(i);
		}
		
		//출력
		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void run(int i) { //i:본인, friend:친구, friend2:친구의 친구
		if(visited[i]) return;
		
		//자신의 방문처리
		visited[i] = true;
		int friend = list[i].remove(0); //본인리스트에서 친구를 제거 및 반환
		
		//친구의 방문처리(친구를 얼리어답터로 선택)
		if(!visited[friend]) {
			visited[friend] = true;
			ans++;			
		}
		list[friend].remove(list[friend].indexOf(i)); //친구의 리스트에서 본인을 제거
		
		//친구의 나머지 친구가 한 명 남았으면 실행
		if(list[friend].size() == 1) {
			int friend2 = list[friend].remove(0); //친구의 리스트에서 '친구의 친구'를 제거 및 반환
			list[friend2].remove(list[friend2].indexOf(friend)); //'친구의 친구'리스트에서 친구를 제거
			if(list[friend2].size() == 1) run(friend2); //'친구의 친구'의 나머지 친구가 한 명 남았으면 friend2를 본인으로 재귀실행
		}
	}
}

dkscltks 1년 전 2

1 6

6 7

1 3

6 8

8 5

5 4

4 9

4 10

9 2

rightAnswer = 5

wrongAnswer = 4

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

문제

문제

출처

ICPC

반례 질문드려요 (+지금까지 나온 반례 정리)

kku64r 1년 전 5

dkscltks 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말