글 읽기 - 자바 40%에서 시간초과가 나는데 이유를 모르겠습니다

tomybaru 3년 전 0

게시판에 올라온 반례들에 답도 맞고 StringTokenizer도 썼는데 40%에서 자꾸 시간 초과가 뜨네요 ㅜㅜ.. 이유가 뭘까요

알려주시면 감사하겠습니다

package basic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int N,M;
	static int [][]map;
	static boolean [][] v;
	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());
		map = new int [M][N];
		v = new boolean[M][N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < N; j++) {
				map[i][j] =Integer.parseInt(st.nextToken());
				
			}
		}//end for
		//모두익음체크함수
		//모두익었다 -> 0이 하나도없다 -> false
		if(!check()) {
			System.out.println(0);
		}else {
			
			int res= bfs();
			//모두익음체크함수
			//0이 하나라도 있다 ->모두익지않았다 -> 다 익힐수없다 -> true
			//다익었다 -> 0이 하나도없다 -> false
			if(check()) {
				System.out.println(-1);
			}else {
				System.out.println(res);
			}
		}
	}
	static class Pos{
		int r,c;

		public Pos(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	private static int bfs() {
		Queue <Pos> Q = new LinkedList<>();
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
			if(	map[i][j] == 1) {
				v[i][j] = true;
				Q.add(new Pos(i,j));
			}
				
			}
		}//end for
		
		int date =1;
		
		while(!Q.isEmpty()) {
			
			int size = Q.size();
			
			for (int s = 0; s < size; s++) {
				
				Pos now = Q.poll();
				
				for (int d = 0; d < 4; d++) {
					int nr = now.r + dr[d];
					int nc = now.c + dc[d];
					if(nr>=0 && nr<M && nc>=0 && nc<N && !v[nr][nc] &&map[nr][nc]==0) {
						v[nr][nc]= true;
						map[nr][nc]=1;
						Q.add(new Pos(nr,nc));
					}
				}//end for
				
			}
			//0이 없다면 false->다익은것 탈출하자!
			if(!check()) return date;
			//System.out.println(date);
			//print();
			date++;
		}
		return date;
	}
	//모두익음함수
	static boolean check() {
		boolean flag = false;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
			if(	map[i][j] == 0 ) flag = true;
			//0이 한번이라도있으면 true -> 모두 익어있지 않음.
			//0이 한번이라도 있으면 true-> 모두 익지 못한것

			}
		}return flag;
	}
	static void print() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j]+" ");
				
			}System.out.println();
		}
	}
}

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

문제

문제

출처

ICPC

자바 40%에서 시간초과가 나는데 이유를 모르겠습니다

tomybaru 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말