글 읽기 - 시간초과

boompatron 1년 전 0

로직이 잘못된 건지 계속 44% 에서 시간초과가 나네요... 새로운 클래스 때문인지...

ripeDay는 토마토가 익는데까지 걸리는 최소 날짜를 저장하는 배열입니다

익은 토마토가 있는지 탐색을 하다가 익은 토마토가 나오면 BFS 를 호출하고

BFS는 익지 않은 토마토이면서, 이전에 다른 토마토 때문에 더 빨리 익으면 ripeDay를 갱신 안하고, 자신 때문에 안익은 토마토가 더 빨리 익으면

ripeDay를 갱신하는 식으로 구성했는데....

파이썬으로 풀 때는 시간 초과가 안 났는데, 자바로는 시간초과가 나서 질문 드립니다ㅠㅠ

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static StringBuilder sb = new StringBuilder();
    private static int m, n;
    private static int[] dxs = {1, -1, 0, 0}, dys = {0, 0, 1, -1};
    private static int[][] g, ripeDay;
    private static StringTokenizer st;
    public static void main(String args[]) throws IOException {
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        g = new int[n][m];
        ripeDay = new int[n][m];
        for(int i = 0; i < n; i ++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                g[i][j] = Integer.parseInt(st.nextToken());
                ripeDay[i][j] = 123456789;
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == 1){
                    BFS(j, i);
                }
            }
        }

        boolean isAllRipe = true;
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(ripeDay[i][j] == 123456789 && g[i][j] == 0){
                    isAllRipe = false;
                }else if(ripeDay[i][j] > ans && g[i][j] == 0)
                    ans = ripeDay[i][j];
            }
        }
        // System.out.println((isAllRipe) ? ans : -1);
        sb.append((isAllRipe) ? ans : -1).append('\n');
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    private static void BFS(int x, int y){
        ripeDay[y][x] = 0;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(x, y, 0));
        while(!q.isEmpty()){
            Pair curPair = q.poll();
            int a = curPair.first();
            int b = curPair.second();
            int d = curPair.third();

            for(int dir = 0; dir < 4; dir++){
                int nx = a + dxs[dir], ny = b + dys[dir];
                if (inRange(nx, ny) && g[ny][nx] == 0 && ripeDay[ny][nx] > d + 1){
                    q.add(new Pair(nx, ny, d + 1));
                    ripeDay[ny][nx] = d + 1;
                }
            }

        }
    }
    private static boolean inRange(int x, int y){
        return 0 <= x && x < m && 0 <= y && y < n;
    }
}
class Pair{
    int x, y, z;
    public Pair(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
    public Integer first(){
        return this.x;
    }
    public Integer second(){
        return this.y;
    }
    public Integer third(){
        return this.z;
    }
}

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

문제

문제

출처

ICPC

시간초과

boompatron 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말