글 읽기 - 자바 반례를 못찾겠습니다 ㅜㅜ

jeong220722 1년 전 0

예제도 넣어보고 추가로 다른 값들도 넣어봤는데, 정상출력이 됩니다.

혹시 반례를 알수있을까요? ㅜㅜ

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

public class Main {

	public static boolean arr[][];
	public static int count;
	public static int M, N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Integer> output = new ArrayList<Integer>();
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		arr = new boolean[M][N];
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int x_min = Math.min(x1, x2);
			int x_max = Math.max(x1, x2);
			int y_min = Math.min(y1, y2);
			int y_max = Math.max(y1, y2);
			
			for(int j = x_min; j < x_max; j++) {
				for(int k = y_min; k < y_max; k++) {
					arr[k][j] = true;
				}
			}
		}
		
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				if(!arr[i][j]) {
					count = 0;
					dfs(i, j);
					output.add(count);
				}
			}
		}
		
		Collections.sort(output);
		
		for(int i = 0; i < output.size(); i++) {
			bw.write(output.get(i) + " ");
		}
		
		bw.write("\n");
		bw.flush();
		bw.close();
		br.close();
		
	}
	
	public static void dfs(int y, int x) {
		count++;
		arr[y][x] = true;
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		
		for(int i = 0; i < 4; i++) {
			int X = x + dx[i];
			int Y = y + dy[i];
			
			if(X >= 0 && X < N && Y >= 0 && Y < M && !arr[Y][X]) {
				dfs(Y, X);
			}
		}
	}

}

vanava 1년 전 0

코드를 돌려보지는 않았지만 간단히 살펴보았을때 구역이 몇개인지 출력하는 부분이 없는것 같은데 아닌가요?

jeong220722 1년 전 0

메인함수 밑에 for문 안에 출력하는 코드가 들어있습니다!

vanava 1년 전 0

코드를 돌려보니 구역의 개수를출력하는 부분이 빠져있습니다.

예제코드에서

1 7 13

이렇게 출력되어야 하는데

코드는

1 7 13

3을 빼고 출력하고 있습니다.

jeong220722 1년 전 0

아! 감사합니다!

그부분을 말씀하시는거였군요!

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

문제

문제

출처

ICPC

자바 반례를 못찾겠습니다 ㅜㅜ

jeong220722 1년 전 0

vanava 1년 전 0

jeong220722 1년 전 0

vanava 1년 전 0

jeong220722 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말