글 읽기 - 시간초과

ghddbtjr 2년 전 0

시간초과 문제를 해결할 수 없어 다른 분들의 코드를 참고하여 수정했는데도 시간초과가 발생하네요...

시간 초과가 어느 부분에서 왜 발생하는걸가요?

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

public class Main {
    private static int n, m, cnt;
    private static int[][] map, visited;
    private static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    private static List<Integer> cntList = new ArrayList<>();

    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];
        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());
            }
        }

        int idx = 1;
        visited = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 1 && visited[i][j] == 0) {
                    cnt = 0;
                    dfs(i, j,idx);

                    cntList.add(cnt);
                    idx++;
                }
            }
        }

        int maxSize = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 0) {
                    maxSize = Math.max(maxSize, getUpdatedSize(i, j, idx));
                }
            }
        }

        System.out.println(maxSize);
    }

    private static void dfs(int i, int j, int idx) {
        visited[i][j] = idx;
        cnt++;

        for(int d = 0; d < 4; d++) {
            int ni = i + dir[d][0];
            int nj = j + dir[d][1];

            if(ni < 0 || ni >= n || nj < 0 || nj >= m || map[ni][nj] == 0) continue;
            if(visited[ni][nj] != 0) continue;

            dfs(ni, nj, idx);
        }
    }

    private static int getUpdatedSize(int i, int j, int idx) {
        int size = 1;
        Set<Integer> set = new HashSet<>();

        for(int d = 0; d < 4; d++) {
            int ni = i + dir[d][0];
            int nj = j + dir[d][1];
            if(ni < 0 || ni >= n || nj < 0 || nj >= m || visited[ni][nj] == 0) continue;

            set.add(visited[ni][nj]);
        }

        for(int num : set) {
            size += cntList.get(num-1);
        }

        return size;
    }
}

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

문제

문제

출처

ICPC

시간초과

ghddbtjr 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말