글 읽기 - Java 시간초과 질문.. 고수님들 알려주세요..

rlagjqm2 2년 전 0

아래 코드에서 meltIce() 메소드는 BFS 입니다.

기본적인 로직은 1년(한번)씩 BFS 돌리고 덩어리 체크를 반복하는 것입니다.

근데 큐에 처음에 인덱스를 넣어주기 위한 초기값을 찾는 과정에서

첫번째 코드처럼 init 함수를 따로 만들어서 넣으면 시간초과가 나고

두번째 코드처럼 BFS 메서드 안에서 초기값을 바로 찾고 넣어주면 시간초과가 안납니다..

시간 초과가 나는 이유는 무슨 이유때문인가요?? 자바 고수님들 알려주세요 ㅠㅠ

첫번째 코드 0번라인 ~ 100번라인

두번째 코드 103번라인 ~ 마지막라인

차이점: init()메서드가 첫번째엔 있고, 두번째엔 없음.

//----------------------------------------------첫번째(시간초과)----------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr;
	static int n,m,ans;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static class Vertex{
		int x;
		int y;
		public Vertex(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	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());
		ans = 0;
		arr = new int[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		//------------------------------------------입력-----------------------------------------------
		
		//덩어리 하나 이상 나올때까지 1년(한번)씩 녹이기
		while(true) {
			int[] idx = init();//초기 인덱스
			if(idx[0]==0 && idx[1]==0) ans=0;//초기 인덱스가 0이다 = 얼음 다녹았다.
			if(meltIce(idx[0],idx[1])) break;
			ans++;
		}
		System.out.println(ans);
	}
	
	//초기값 찾아주는 함수
	public static int[] init() {
		int[] idx = new int[2];
		for(int i=1; i<n-1; i++) {
			for(int j=1; j<m-1; j++) {
				if(arr[i][j]!=0) {
					idx[0] = i;
					idx[1] = j;
					return idx;
				}
			}
		}
		return idx;
	}
	
	//BFS(얼음녹이고 덩어리 구분하기)
	public static boolean meltIce(int xidx, int yidx) {
		Queue<Vertex> q = new LinkedList<Vertex>();
		boolean[][] check = new boolean[n][m];
		
		q.add(new Vertex(xidx, yidx));
		check[xidx][yidx] = true;
		
		while(!q.isEmpty()) {
			Vertex curV = q.poll();
			
			for(int i=0; i<4; i++) {
				int nextX = curV.x + dx[i];
				int nextY = curV.y + dy[i];
				
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
					if(arr[nextX][nextY]!=0 && !check[nextX][nextY]) {
						check[nextX][nextY] = true;
						q.add(new Vertex(nextX, nextY));
					}
					if(arr[nextX][nextY]==0 && arr[curV.x][curV.y]-1>=0 && !check[nextX][nextY]) 
						arr[curV.x][curV.y]--;
				}
			}
		}//while
		
        //덩어리 한개이상이면 true 반환
		for(int i=1; i<n-1; i++) {
			for(int j=1; j<m-1; j++) {
				if(arr[i][j]!=0 && !check[i][j]) return true;
			}
		}
		
		return false;
	}
}


//----------------------------------------------두번째(통과)----------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr;
	static int n,m,ans;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static class Vertex{
		int x;
		int y;
		public Vertex(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	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());
		ans = 0;
		arr = new int[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		//------------------------------------------입력-----------------------------------------------
		
        //덩어리 하나 이상 나올때까지 1년(한번)씩 녹이기
		while(true) {
			if(meltIce()) break;
			ans++;
		}
		System.out.println(ans);
	}
    
	//BFS(얼음녹이고 덩어리 구분하기)
	public static boolean meltIce() {
		int[] idx = new int[2];
        //초기 인덱스 찾기
		for(int i=1; i<n-1; i++) {
			for(int j=1; j<m-1; j++) {
				if(arr[i][j]!=0) {
					idx[0] = i;
					idx[1] = j;
					break;
				}
			}
			if(idx[0]!=0 && idx[1]!=0) break;
		}
		
        //초기 인덱스가 0이다. = 얼음 다녹았다.
		if(idx[0]==0 && idx[1]==0) {
			ans=0;
			return true; 
		}
		
		Queue<Vertex> q = new LinkedList<Vertex>();
		boolean[][] check = new boolean[n][m];
		
		q.add(new Vertex(idx[0], idx[1]));
		check[idx[0]][idx[1]] = true;
		
		while(!q.isEmpty()) {
			Vertex curV = q.poll();
			
			for(int i=0; i<4; i++) {
				int nextX = curV.x + dx[i];
				int nextY = curV.y + dy[i];
				
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
					if(arr[nextX][nextY]!=0 && !check[nextX][nextY]) {
						check[nextX][nextY] = true;
						q.add(new Vertex(nextX, nextY));
					}
					if(arr[nextX][nextY]==0 && arr[curV.x][curV.y]-1>=0 && !check[nextX][nextY]) 
						arr[curV.x][curV.y]--;
				}
			}
		}//while
		
        //덩어리 한개이상이면 true 반환
		for(int i=1; i<n-1; i++) {
			for(int j=1; j<m-1; j++) {
				if(arr[i][j]!=0 && !check[i][j]) return true;
			}
		}
		
		return false;
	}
}

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

문제

문제

출처

ICPC

Java 시간초과 질문.. 고수님들 알려주세요..

rlagjqm2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말