글 읽기 - JAVA 시간 초과 질문입니다 ㅠㅠ

mamamau 5년 전 0

BFS 방식으로 처리했는데 시간 초과가 뜨네요...

어느 부분을 최적화 시켜야 할 지 모르겠습니다 ㅠㅠ

import java.util.*;
import java.io.*;

public class Water {
	static int N;
	static int max = 0;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		int[][] map = new int[100][100];
		boolean[][] visited = new boolean[100][100];
		for(int i=0;i<N;i++) {
			String[] s = br.readLine().trim().split(" ");
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(s[j]);
				if(max < map[i][j])
					max = map[i][j];
			}
		}
		
		System.out.println(maxWater(map, visited));
	}
	
	public static int maxWater(int[][] map, boolean[][] visited) {
		int water = 0;
		for(int i=0;i<max;i++) {
			for(int j=0;j<N;j++)
				Arrays.fill(visited[j], false);
			water = Math.max(water, getArea(map, visited,i));
		}
		return water;
	}
	
	public static int getArea(int[][] map, boolean[][] visited, int h) {
		int cnt=0;
		Queue<Point> q = new LinkedList<Point>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j] > h && !visited[i][j]) {
					q.add(new Point(i,j));
					while(!q.isEmpty()) {
						Point p = q.poll();
						visited[p.x][p.y] = true;
						for(int k=0;k<4;k++) {
							int cx = p.x+dx[k];
							int cy = p.y+dy[k];
							if(chk(cx,cy) && !visited[cx][cy] && map[cx][cy] > h)
								q.add(new Point(cx,cy));
						}
					}
					cnt++;
				}
			}
		}
		return cnt;
	}
		

	public static boolean chk(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N;
	}
	public static class Point{
		public int x;
		public int y;
		public Point(int x, int y) {
			this.x =x; this.y = y;
		}
	}
}

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

문제

문제

출처

ICPC

JAVA 시간 초과 질문입니다 ㅠㅠ

mamamau 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말