글 읽기 - [자바] 시간초과가 왜 뜨는걸까요??

mommoo 3년 전 0

BFS 탐색에, 큐에서 넣으면서 미리 체크를 하는 방식으로 시간 복잡도를 최적화 했다고 생각이 드는데요...

왜 시간초과가 뜨는걸까요??

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    private static final int UNDER_COOK_TOMATO = 0;
    private static final int ROTTEN_TOMATO = -1;
    private static final int COOK_TOMATO = 1;

    private static final int[] dx = {1, 0 , -1, 0};
    private static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        int maxCol = Integer.parseInt(tokenizer.nextToken());
        int maxRow = Integer.parseInt(tokenizer.nextToken());

        int[][] tomatoes = createTomatoes(br, maxRow, maxCol);

        TomatoCookTracker tomatoCookTracker = new TomatoCookTracker(tomatoes);
        while (tomatoCookTracker.hasMoreCook()) {
            tomatoCookTracker.cook();
        }

        System.out.println(tomatoCookTracker.getDays());
    }

    private static int[][] createTomatoes(BufferedReader br, int maxRow, int maxCol) throws IOException {
        int[][] tomatoes = new int[maxRow][maxCol];

        for (int row = 0; row < maxRow; row++) {
            StringTokenizer tomatoTokenizer = new StringTokenizer(br.readLine());
            int col = 0;
            while (tomatoTokenizer.hasMoreTokens()) {
                tomatoes[row][col++] = Integer.parseInt(tomatoTokenizer.nextToken());
            }
        }

        return tomatoes;
    }

    private static class RowAndCol {
        private final int row;
        private final int col;

        public RowAndCol(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public RowAndCol move(int additionalRow, int additionalCol) {
            return new RowAndCol(this.row + additionalRow, this.col + additionalCol);
        }

        public boolean isInValid(int maxRow, int maxCol) {
            return !(0 <= row && row < maxRow && 0 <= col && col < maxCol);
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof RowAndCol))
                return false;
            RowAndCol rowAndCol = (RowAndCol) o;
            return row == rowAndCol.row &&
                   col == rowAndCol.col;
        }
    }

    private static class TomatoCookTracker {
        private int days = 0;
        private final Set<RowAndCol> underCookTomatoes = new HashSet<>();
        private final Queue<RowAndCol> queue1 = new LinkedList<>();
        private final Queue<RowAndCol> queue2 = new LinkedList<>();
        private final int[][] tomatoes;

        private TomatoCookTracker(int[][] tomatoes) {
            this.tomatoes = tomatoes;
            checkTomatoes();
        }

        private void checkTomatoes() {
            for (int row = 0 ; row < tomatoes.length; row++) {
                for (int col = 0 ; col < tomatoes[0].length; col++) {
                    checkTomato(row, col);
                }
            }
        }

        private void checkTomato(int row, int col) {
            int tomato = tomatoes[row][col];
            if (UNDER_COOK_TOMATO == tomato) {
                underCookTomatoes.add(new RowAndCol(row, col));
                return;
            }

            if (COOK_TOMATO == tomato) {
                queue1.offer(new RowAndCol(row, col));
            }
        }

        public boolean hasMoreCook() {
            return !(queue1.isEmpty() && queue2.isEmpty()) && !underCookTomatoes.isEmpty();
        }

        private void cookTomato(RowAndCol rowAndCol) {
            tomatoes[rowAndCol.row][rowAndCol.col] = COOK_TOMATO;
        }

        private boolean doesNotCookTomato(RowAndCol rowAndCol) {
            int maxRow = tomatoes.length;
            int maxCol = tomatoes[0].length;

            if (rowAndCol.isInValid(maxRow, maxCol)) {
                return true;
            }

            int foundTomato = tomatoes[rowAndCol.row][rowAndCol.col];
            return (COOK_TOMATO == foundTomato) || (ROTTEN_TOMATO == foundTomato);
        }

        public void cook() {
            days++;
            Queue<RowAndCol> targetQueue = queue1.isEmpty() ? queue2 : queue1;
            Queue<RowAndCol> emptyQueue = queue1.isEmpty() ? queue1 : queue2;

            while (!targetQueue.isEmpty()) {
                RowAndCol rowAndCol = targetQueue.poll();
                for (int i = 0; i < 4; i++) {
                    RowAndCol nextRowAndCol = rowAndCol.move(dx[i], dy[i]);
                    if (doesNotCookTomato(nextRowAndCol)) {
                        continue;
                    }

                    emptyQueue.offer(nextRowAndCol);
                    cookTomato(nextRowAndCol);
                    underCookTomatoes.remove(nextRowAndCol);
                }
            }
        }

        public int getDays() {
            return underCookTomatoes.isEmpty() ? days : -1;
        }
    }
}

djm03178 3년 전 1

다른 부분에 문제가 없다면 HashSet이 느려서일 수도 있습니다. 평균이 O(1)이라고는 하지만 실제로는 많은 충돌들과 그를 피하기 위한 복잡한 해싱 과정으로 매우 느려지는 자료구조입니다.

mommoo 3년 전 0

@djm03178

님 감사합니다. 배열로 바꿔서 푸니까 맞았네요.

물론, HashSet이 느릴 수 있다는건 알고 있었지만 이렇게 문제에 영향을 주는건 좀 아쉽네요ㅠ...

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

문제

문제

출처

ICPC

[자바] 시간초과가 왜 뜨는걸까요??

mommoo 3년 전 0

djm03178 3년 전 1

mommoo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말