글 읽기 - [2573 빙산] _ 시간초과 이유가 궁금합니다.(62% TLE)

kimby469 2년 전 0

해당 빙산의 높이가 0이아닌 경우 list에 담았습니다.(각 가로 세로 좌표와 높이)

while(true)

{

< 영역배정과 체크>

for(리스트의 사이즈만큼 각 영역을 할당)

{

영역이 할당 안되어 있으면 areaAssign 함수

영역이 할당 되어있고 count 값이 3이면 이 영역은 분리되어있는것으로 프로그램을 종료합니다.

}

<빙산이 녹을 때>

녹아도 남는 빙하, 녹고 없어지는 빙하의 리스트를 따로 담았습니다.

마지막에 없어지는 빙하 리스트 크기만큼 돌면서 map[][] 배열을 0으로 만들어줍니다.

}

저는 2차원 배열 300 * 300 칸을 돌지않고

기존 리스트를 중간에 삭제하는 것도 아니고 그냥 옮겨 닮기만 했는데 시간초과가 62%에서 발생합니다.

왜 시간초과를 맞는지 궁금합니다.

제가 생각하기에는 리스트 최대 사이즈가 300이므로 선형시간을 갖는데 있어 왜 초과가 나는지 궁급합니다. ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,m,map[][],area[][],melt[][];
    static int dy[]={-1,1,0,0};
    static int dx[]={0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        map=new int[n][m];

        List<Node> list=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]!=0)
                {
                    list.add(new Node(i,j,map[i][j]));
                }
            }
        }
        int t=0;
        int cnt=0;
        while (true)
        {
            t++;
            cnt=1;
            area=new int[n][m];
            // 최대 9,000,000 칸  -> list 300칸
            for (Node node : list) {
                if(area[node.y][node.x]==0) {
                    areaAssign(node.y, node.x, cnt);
                    cnt++;
                }

                if(cnt>2)
                {
                    System.out.println(t-1);
                    return;
                }
            }


            List<Node> newList=new ArrayList<>(); // 살아남는 빙하
            List<Node> removeList=new ArrayList<>(); // 다 녹는 빙하.
            for (Node ice : list)
            {
                Node cur = ice;
                int count=0;
                for (int i = 0; i < 4; i++) {
                    int ny=dy[i]+cur.y;
                    int nx=dx[i]+cur.x;
                    if(ny<0 || nx<0 && ny>=n && nx>=m)
                        continue;
                    if(map[ny][nx]==0)
                        count++;
                }
                int gap = cur.h - count;
                if(gap>0)
                {
                    newList.add(new Node(cur.y,cur.x,gap));
                    map[cur.y][cur.x]=gap;
                }
                else
                {
                    removeList.add(new Node(cur.y,cur.x));
                }
            }
            for (Node node : removeList) { // 빙하 원본 배열 갱신
                map[node.y][node.x]=0;
            }
            list.clear(); 
            list.addAll(newList);
        }
    }
    static void areaAssign(int y,int x,int number)
    {
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(y,x));
        area[y][x]=number;
        while (!q.isEmpty())
        {
            Node cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int ny=dy[i]+cur.y;
                int nx=dx[i]+cur.x;
                if(ny<0 || nx<0 && ny>=n && nx>=m)
                    continue;
                if(area[ny][nx]!=0)
                    continue;
                if(map[ny][nx]==0)
                    continue;

                area[ny][nx]=number;
                q.offer(new Node(ny,nx));
            }
        }
    }
    static class Node{
        private int y,x,h;

        public Node(int y,int x)
        {
            this.y=y;
            this.x = x;
        }
        public Node(int y, int x,int h) {
            this.y = y;
            this.x = x;
            this.h=h;
        }
    }
}

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