글 읽기 - 시간초과라고 뜨는데 어디를 수정해야할지 모르겠습니다

dubu4050 3년 전 0

예제는 일단 다 돌아가는데

2%에서 시간초과라고 뜹니다..ㅠㅠ

어디가 문제인지 모르겠어요..

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] arr;
    static int notTomato=0;
    static int N,M;
    static Queue<Pair> queue = new LinkedList<>();

    static class Pair{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void bfs(){
        List<Pair> list = new ArrayList<>();
        int max = 0;
        int cnt = 0;
        while(!queue.isEmpty()){
            Pair pair = queue.poll();
            if(pair.x!=0)
                list.add(new Pair(pair.x-1, pair.y));
            if(pair.y!=0)
                list.add(new Pair(pair.x, pair.y-1));
            if(pair.x<M-1)
                list.add(new Pair(pair.x+1, pair.y));
            if(pair.y<N-1)
                list.add(new Pair(pair.x, pair.y+1));

            Pair tmp;
            for(int i=0;i<list.size();i++) {
                tmp = list.get(i);
                if(arr[tmp.y][tmp.x]!=0)
                    continue;
                queue.add(tmp);
                cnt++; // 안익음 -> 익음 카운트
                max = Math.max(max, arr[pair.y][pair.x]+1);
                arr[tmp.y][tmp.x]=arr[pair.y][pair.x]+1;
            }
        }

        if(cnt!= M*N-notTomato) // 안익은 토마토 남은 경우
            System.out.println(-1);
        else if( max == 0)
            System.out.println(0);
        else
            System.out.println(max-1);
    }

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");

        M = Integer.parseInt(input[0]); // v
        N = Integer.parseInt(input[1]); // h

        arr = new int[N][M];
        for(int i=0;i<N;i++){
            input=br.readLine().split(" ");
            for(int j=0;j<M;j++) {
                int tmp = Integer.parseInt(input[j]);
                arr[i][j] = tmp;
                if(tmp!=0) {
                    notTomato++;
                    if (tmp != 1)
                        continue;
                    queue.add(new Pair(j, i));
                }
            }
        }
        bfs();
    }
}

dltmdals0608 3년 전 0

예제 입력은 다 잘 돌아가나요??

dubu4050 3년 전 0

예제는 잘 돌아갑니다!

자문자답이지만 list.clear()를 안써서 시간초과가 난거였습니다..ㅠㅠ

고민해주신 분들 다 감사합니다!

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

문제

문제

출처

ICPC

시간초과라고 뜨는데 어디를 수정해야할지 모르겠습니다

dubu4050 3년 전 0

dltmdals0608 3년 전 0

dubu4050 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말