글 읽기 - 시간초과 도와주세요.

yoonys427 5년 전 0

시간초과가 나는데 어딜 고쳐야할지 모르겠습니다.

도와주세요 ㅠㅠ

import java.util.*;

public class Main {
	
	public static int n, l, r;
	public static int[][] map;
	public static int[] dx = {0, 0, -1, +1};
	public static int[] dy = {-1, +1, 0, 0,};
	
	public static boolean moving(int[][] input) {
		boolean isUpdate = false;
		
		int[][] check = new int[n][n];
		int grp = 0;
		
		for (int y=0; y<n; y++) {
			for (int x=0; x<n; x++) {
				if (check[y][x] == 0)
					grp++;
				union(input, check, x, y, grp);
			}
		}
		
		for (int i=1; i<=grp; i++) {
			int sum = 0;
			int count = 0;
			
			for (int y=0; y<n; y++) {
				for (int x=0; x<n; x++) {
					
					if (check[y][x]==i) {
						
						sum += input[y][x];
						count++;
					}
					
				}
			}
			
			int mean = sum/count;
			
			for (int y=0; y<n; y++) {
				for (int x=0; x<n; x++) {
					
					if (check[y][x]==i) {
						if (input[y][x] != mean) {
							input[y][x] = mean;
							isUpdate=true;
						}
					}
					
				}
			}
			
		}
		return isUpdate;
	}
	
	
	
	public static void union(int[][] input, int[][] check, int startX, int startY, int grp) {
		
		if (check[startY][startX] > 0) {
			return;
		}
		
		check[startY][startX] = grp;
		
		for (int dir=0; dir<4; dir++) {
			int nextX = startX + dx[dir];
			int nextY = startY + dy[dir];
			
			if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
				int gap = Math.abs(input[startY][startX] - input[nextY][nextX]);
				if (gap >= l && gap <= r && check[nextY][nextX] == 0)
					union(input, check, nextX, nextY, grp);
			}
			
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		l = sc.nextInt();
		r = sc.nextInt();
		
		map = new int[n][n];
		
		for (int y=0; y<n; y++) {
			for (int x=0; x<n; x++) {
				map[y][x] = sc.nextInt();
			}
		}
		
		boolean isUpdate = true;
		int count = 0;
		while(isUpdate) {
			isUpdate = moving(map);
			if(isUpdate)
				count++;
		}
		
		System.out.println(count);
	}
}

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

문제

문제

출처

ICPC

시간초과 도와주세요.

yoonys427 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말