글 읽기 - 토마토 문제 계속 시간초과가 뜹니다 ㅠㅠ 주석있어요 JAVA

jakgon 2년 전 0

어떤걸 해봐도 자꾸 시간초과가 뜹니다 ㅠㅠ
어떻게 해결해야할까요..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        short x = 0;
        short y = 0;

        StringTokenizer st = new StringTokenizer(sc.readLine());
        x = Short.parseShort(st.nextToken());
        y = Short.parseShort(st.nextToken());

        //총 토마토 그리드 저장용 어레이
        Node[][] nodes = new Node[x][y];
        for (short i = 0; i < x; i++) {
            for (short j = 0; j < y; j++) {
                nodes[i][j] = new Node(i, j);
            }
        }
        short test;
        
        //임시변수
        Node currs;
        //총 토마토 수
        short tomatoCnt = 0;
        //먼저 토마토수 == 익은수 인지 확인차
        short miniCheck = 0;
        List<Node> startNodes = new ArrayList<>();
        for (short i = 0; i < y; i++) {
            st = new StringTokenizer(sc.readLine());
            for (short j = 0; j < x; j++) {
                test = Short.parseShort(st.nextToken());
                currs = nodes[j][i];
                if (test != -1)
                    tomatoCnt++;
                if (test == 1) {
                    currs.checked = true;
                    startNodes.add(currs);
                    miniCheck++;
                } else {
                    currs.exists = test != -1;
                }
            }
        }
        sc.close();

        if (miniCheck == tomatoCnt) {
            System.out.println(0);
            return;
        }
        //N^2
        for (short i = 0; i < x; i++) {
            for (short j = 0; j < y; j++) {
                Node curr = nodes[i][j];
                //3,4번째 패러미터에 집어넣을 수 있으면 넣고 아니면(범위밖이거나 빈칸이거나.. 검사)
                //BFS 전에 사전에 관계에 대한 LinkedList 만드는 과정
                addIfCan(nodes, curr, (short) (i + 1), j, x, y);
                addIfCan(nodes, curr, (short) (i - 1), j, x, y);
                addIfCan(nodes, curr, i, (short) (j - 1), x, y);
                addIfCan(nodes, curr, i, (short) (j + 1), x, y);
            }
        }
        short max = -1;
        
        //시간초과때문에 O(N) -> O(N..보단 낮은값) 으로 바꿔보려고 시도한 흔적
        //원래 이 다음다음에 N^2라고 주석쳐져있는 부분 포문이 이중루프었음 (이중배열)
        HashSet<Node> indexedNodes = new HashSet<>();

        for (Node n : startNodes) {
            n.stackSize = 1;
            BFS(n, indexedNodes);
            for (Node indexedNode : indexedNodes) {
                indexedNode.visit = false;
            }
        }

        short counter = 0;
        //N^2 , DFS 돌리고 난 후 최단거리의 최댓값과 익은 토마토 개수 세기.
        //stackSize의 default는 null인데 null이 아니란건 DFS에서 긁고 지나갔단 소리니 익었음
        for (Node node1 : indexedNodes) {
            if (node1.stackSize != null || node1.checked) {
                if (node1.stackSize != null && max < node1.stackSize) {
                    max = node1.stackSize;
                }
                counter++;
            }
        }
        if (counter < tomatoCnt) {
            System.out.println(-1);
        } else {
            System.out.println((max - 1));
        }

    }

    public static void BFS(Node curr, HashSet<Node> indexed) {
        Queue<Node> currentQueue = new LinkedList<>();
        currentQueue.add(curr);
        indexed.add(curr);
        Node iter;
        short next;
        while (!currentQueue.isEmpty()) {
            iter = currentQueue.poll();
            next = (short) (iter.stackSize + 1);
            if (iter.lists != null) {
                for (Node list : iter.lists) {
                    if (list.stackSize != null && list.stackSize < next) {
                        continue;
                    }
                    if (!list.visit) {
                        list.visit = true;
                        indexed.add(list);
                        if (!list.checked) {
                            currentQueue.add(list);
                            list.stackSize = next;
                        }
                    }
                }
            }

        }

    }

    public static void addIfCan(Node[][] nodes, Node curr, short x, short y, short x_max, short y_max) {
        if (x < 0 || x >= x_max || y < 0 || y >= y_max)
            return;
        Node target = nodes[x][y];
        if (target.exists) {
            curr.addNode(target);
        }
    }

    static class Node {
        //노드의 좌표
        short x, y;
        //방문했는지 아닌지, 애초에 익었는지 아닌지, 빈칸인지 아닌지
        boolean visit = false, checked = false, exists = false;
        //인접 노드들을 담은 리스트
        ArrayList<Node> lists = null;
        //해당 노드의 깊이 (끝까지 널이면 어떤 DFS도 이 노드를 안쓸고 갔다는 소리..)
        Short stackSize = null;

        Node(short x, short y) {
            this.x = x;
            this.y = y;
        }

        void addNode(Node n) {
            if (this.lists == null)
                this.lists = new ArrayList<>(8);
            lists.add(n);
        }
    }
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

토마토 문제 계속 시간초과가 뜹니다 ㅠㅠ 주석있어요 JAVA

jakgon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
