글 읽기 - 시간초과가 발생하네요.. 어디서 시간을 줄여야 할까요?

wow1514 8년 전 0

답은 나오는거 같은데 시간초과 뜨네요.. 정올에서 한 케이스에서 시간초과가 뜨고

백준에서도 50%까지 채점하다가 시간초과가 발생합니다.

시간을 줄일만한 구석이 있으면 지적 해주세요.. 제 코드라그런지

전 어디서 더 줄여야 할지 잘 안보이네요 ㅠㅠ

import java.util.Scanner;

public class Main{
	static int N,M;
	static int[][] arr;
	static int[][] visited;
	static int[] dx={-1,1,0,0};
	static int[] dy={0,0,-1,1};
	static int time = 0;
	static int ice = 0;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		arr= new int[N+1][M+1];
		int[] start = new int[2];
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				arr[i][j] = sc.nextInt();
				if(arr[i][j] != 0){
					ice += arr[i][j];
					start[0] = i;
					start[1] = j;
				}
			}
		}
		
		//모든 빙산이 녹을때 까지 반복
		while(ice >= 0){
			//빙산 덩어리가 나누어 졌는지 확인
			if(isSeperate()){
				System.out.println(time);
				break;
			}
			visited = new int[N+1][M+1];
			time++;
			//빙산을 탐색하며 물에 닿는 빙산의 높이를 낮춰준다.
			start = decrease(BFS(start[0],start[1]));
		}
		
		if(ice <= 0)
			System.out.println(0);
		
		sc.close();
	}
	//input
	//startX : 탐색을 시작할 행	startY : 탐색을 시작할 열
	//return
	//int[][] ar : 빙산과 인접한 물의 갯수
	static int[][] BFS(int startX, int startY){
		Queue q = new Queue(100000);
		int[][] ar = new int[N+1][M+1];
		visited[startX][startY] = 1;
		q.push(startX);
		q.push(startY);
		
		while(!q.isEmpty()){
			int x = q.pop();
			int y = q.pop();
			
			for(int i = 0; i < 4; i++){
				int newX = x + dx[i];
				int newY = y + dy[i];
				
				if(newX >= 1 && newX <= N && newY >= 1 && newY <= M){
					if(arr[newX][newY] == 0){
						ar[x][y]--;
					}
					else if(arr[newX][newY] != 0 && visited[newX][newY] == 0){
						visited[newX][newY] = 1;
						q.push(newX);
						q.push(newY);
					}
				}
				
			}
		}
		
		return ar;
	}
	//빙산을 탐색하며 인접해있으면 bfs 한번으로 탐색이 가능 -> count == 1
	//빙산이 두 덩어리 이상이면 덩어리 갯수만큼 count가 늘어난다.
	static boolean isSeperate(){
		visited = new int[N+1][M+1];
		int count = 0;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				if(arr[i][j] != 0 && visited[i][j] == 0){
					BFS(i,j);
					count++;
				}
			}
		}
		
		if(count > 1){
			return true;
		}
		else
			return false;
	}
	//bfs 메소드에서 리턴 받은 빙산과 인접한 물의 갯수
	//input 배열의 값만큼 빙산에 더해주면 감소된 높이가 된다.
	//return
	//다음 탐색에서 시작할 빙산의 위치
	static int[] decrease(int[][] ar){
		//System.out.println(time);
		int[] start = new int[2];
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				arr[i][j] += ar[i][j];
				ice -= ar[i][j];
				if(arr[i][j] <= 0)
					arr[i][j] = 0;
				else{
					start[0] = i;
					start[1] = j;
				}
				//System.out.print(arr[i][j]+" ");
			}
			//System.out.println();
		}
		//System.out.println();
		return start;
	}
	
}
class Queue{
	private int front;
	private int rear;
	private int max_size;
	private int[] arr;
	
	public Queue(int size){
		front = -1;
		rear = -1;
		max_size = size;
		arr = new int[max_size];
	}
	
	public void push(int item){
		arr[++rear] = item;
	}
	
	public int pop(){
		return arr[++front];
	}
	
	public int peek(){
		int index = front;
		return arr[++index];
	}
	
	public boolean isEmpty(){
		return (front == rear);
	}
}

wow1514 8년 전 1

첫번째 행과 열, 마지막 행과 열은 무조건 바다이므로 bfs 든 dfs든 탐색에서 제외합니다.

빙산이 나누어져있는지 검사할때 탐색함수를 두번돌면 무조건 빙산이 나누어진것이므로

for문이 끝날때까지 기다리는 것이 아니라 두번째 탐색하려고 진입하는 순간 true를 리턴하고 함수를 종료 시킵니다.

감소시키는 decrease함수도 따로만드는 것이아니라 bfs함수를 돌면서 빙산 주위의 바다개수를 구하여 저장한뒤 모든 탐색이 끝난 후

바다 개수만큼 빙산 높이를 낮춰주었습니다.

여기서 for문을 이용하여 x+1,x-1,y+1,y-1을 탐색하는 것보다 if문을 이용하는게 더 빠릅니다.

이렇게 하니 간신히 시간초과는 면하네요. 대략 500ms ~ 700ms 사이로 나옵니다.

wow1514 8년 전 0

위의 코드는 시간초과가 안떠도 틀린답이 나오는 코드입니다.

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

문제

문제

출처

ICPC

시간초과가 발생하네요.. 어디서 시간을 줄여야 할까요?

wow1514 8년 전 0

wow1514 8년 전 1

wow1514 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말