글 읽기 - 시간초과가 나오는데

konis123 6년 전 0

어디부분떄문에 시간초과가 나오는건가요.. 답은 일단은 잘 나오는거같은데...

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 algo2468 {

	static int n;
	static Queue<Integer> q;
	static int[][] map;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//n = Integer.parseInt(br.readLine());
		n = scan.nextInt();
		
        //StringTokenizer st = new StringTokenizer(br.readLine());
       
        //int a = Integer.parseInt(st.nextToken());

		
		map = new int[n*n+1][2];
		int maxNum = 0;

		q = new LinkedList<Integer>();
		
		/////
		int[] ans = new int[101];
		for(int i=0;i<101;i++){
			ans[i] = 0;
		}
		/////
		
		
		int in_min=0,in_max=100;
		for(int i=1;i<=n*n;i++){
			map[i][0] = scan.nextInt();
			map[i][1] = 0;	//0이면 안잠긴거 1이면 잠긴거
			in_min = Math.min(map[i][0], in_min);
			in_max = Math.max(map[i][0], in_max);
			
			ans[map[i][0]] = 1;
			
		}
		/*
		for(int i=in_min;i<=in_max;i++){
		//for(int i=1;i<=100;i++){
			//int temp = getIslandNum(map,i);
			int temp = BFS(getIslandNum(map,i));
			maxNum = Math.max(temp,maxNum);
		}*/
		
		for(int i=1;i<=100;i++){
			if(ans[i] == 1){
				int temp = BFS(getIslandNum(map,i));
				maxNum = Math.max(temp,maxNum);
			}
		}
		
		
		System.out.println(maxNum);
		
	}
	
	public static int[][] getIslandNum(int[][] map, int sn){	//n이하는 물에잠김
		for(int i=1;i<=n*n;i++){
			if(map[i][0] <= sn){
				map[i][1] = 1;
			}else{
				map[i][1] = 0;
			}
		}
		//int num = BFS(map);
		
		//return num;
		return map;
	}

	public static int BFS(int[][] map){
		int count = 0;
		for(int i=1;i<=n*n;i++){
			//if(map[i][1] == 2 || map[i][1] == 1)	continue;
			if(map[i][1] != 0)	continue;
			else{	//map[i][1] == 0 일때
				map[i][1] = 2;
				if(i%n != 0 && (i+1<n*n) && map[i+1][1] == 0){
					q.add(i+1);
				}
				if(i%n != 1 && (i-1>0) && map[i-1][1] == 0){
					q.add(i-1);
				}
				if(i+n<=n*n && map[i+n][1] == 0){
					q.add(i+n);
				}
				if(i-n>0 && map[i-n][1] == 0){
					q.add(i-n);
				}
			}
			
			int temp;
			while(!q.isEmpty()){
				temp = q.poll();
				map[temp][1] = 2;
				if(temp%n != 0 && temp+1<n*n && map[temp+1][1] == 0){
					q.add(temp+1);
				}
				if(temp%n != 1 && temp-1>0 && map[temp-1][1] == 0){
					q.add(temp-1);
				}
				if(temp+n<=n*n && map[temp+n][1] == 0){
					q.add(temp+n);
				}
				if(temp-n>0 && map[temp-n][1] == 0){
					q.add(temp-n);
				}
			}
			
			count++;
		}
		
		return count;
	}
	
}

42desix 6년 전 0

일단 시간초과 이전에 반례가 있습니다.

2 2

같은 경우 강수량이 0이나 1이면 결과가 1이 나와야 되는데 0이 나오네요.

konis123 6년 전 0

42desix//친구야 그건 위에서 제가 여러가지 시간줄이려고한 코드중에서 문제가있어서 그런거같어..... 그냥 1~100 까지 for문에서 돌리면 답은 올바로 나오는데 시간초과가 나온다...........................ㅜㅜㅜㅜ 메소드중에 시간잡아먹는게 있는거같은데 그중에서 뭐가문젠지 모르겠네..

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

문제

문제

출처

ICPC

시간초과가 나오는데

konis123 6년 전 0

42desix 6년 전 0

konis123 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말