글 읽기 - java 12% 틀림

yjwhite1004 2년 전 0

r, c 고려해서 너무 복잡하게 푼 감이 없지 않아있지만 ㅠㅠ

시간초과 피하려고 hash까지 썼는데

자꾸 12퍼센트에서 틀렸다고 뜨네요 ㅠㅠ

반례

5 4

0 1

1 2

2 3

3 0

정답 : 0

으로 잘 나오는데 어디가 문제일까요?ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int answer = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		HashSet<Integer> person = new HashSet<>();
		boolean[][] friend = new boolean[N][N];
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			friend[a][b] = true;
			friend[b][a] = true;
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(friend[i][j] == true) {
					person.add(i);
					person.add(j);
					
					dfs1(i, 0, person, friend);
					dfs2(j, 0, person, friend);
					break;
				}
			}
		}
		
		System.out.println(answer);
	}
	
	private static void dfs1(int r, int depth, HashSet person, boolean[][] friend) {
		for(int i=0; i<N; i++) {
			if(friend[r][i] == true) {
				friend[r][i] = false;
				friend[i][r] = false;
				
				person.add(i);
				
				if(person.size()>=5 && depth+1>=4) {
					answer = 1;
					break;
				}
				
				dfs1(i, depth+1, person, friend);
			}
		}
	}
	
	private static void dfs2(int c, int depth, HashSet person, boolean[][] friend) {
		for(int i=0; i<N; i++) {			
			if(friend[i][c] == true) {
				friend[i][c] = false;
				friend[c][i] = false;
				
				person.add(i);
				
				if(person.size()>=5 && depth+1>=4) {
					answer = 1;
					break;
				}
				
				dfs2(i, depth+1, person, friend);
			}
		}
	}
}

ny2485 1년 전 0

저 반례 정답 1아닌가요?

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

문제

문제

출처

ICPC

java 12% 틀림

yjwhite1004 2년 전 0

ny2485 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말