글 읽기 - 2617 구슬찾기 반례부탁드리겠습니다

nhouyng 6년 전 0

방향을 1,2로 구분하고

자기보다 무겁거나 가벼운 개수를 hashSet(중복제거)에 저장해서

그 크기가 n/2+1 보다 크거나 같으면 중간무게의 구슬이 될 수 없다고 판단했습니다.

이해가 잘못된건지 아니면 코드에 문제가 있는지 반례좀 부탁드립니당

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

public class Main {

	public static int[][] mat;
	public static int n, m;
	public static int std;
	public static HashSet<Integer> hashSet = new HashSet<>();

	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());
		mat = new int[n + 1][n + 1];
		std = n / 2 + 1;

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			mat[a][b] = 1;
			mat[b][a] = 2;
		}

		int result = 0;
		for (int i = 1; i <= n; i++) {

			hashSet.clear();
			dfs(i, 1);
			if(hashSet.size() >= std)
				result++;
			else {
				hashSet.clear();
				dfs(i, 2);
				
				if(hashSet.size() >=std)
					result++;
			}
		}

		System.out.println(result);
	}

	public static void dfs(int startIndex, int k) {

		if (hashSet.size() >= std)
			return;

		for (int i = 1; i <= n; i++) {
			if (mat[startIndex][i] == k) {
				hashSet.add(i);
				dfs(i, k);
			}
		}
	}
}

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

문제

문제

출처

ICPC

2617 구슬찾기 반례부탁드리겠습니다

nhouyng 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말