글 읽기 - 시간초과인데 어느 부분 때문일까요?

(追記) (追記ここまで)

시간초과인데 어느 부분 때문일까요?

16932번 - 모양 만들기

gkdud583 4년 전 1

검색을 해보았는데 문제를 해결하는 방법은 같은거 같은데 왜 제출하면 시간초과가 나오는지 모르겠어요 ᅲᅲ

map값이 0일경우 상하좌우를 확인하고 그룹 크기를 더해주면서 최댓값을 구하는 식으로 짰습니다.

어느 부분때문에 시간초과가 나올까요?

import java.util.*;
class Main{
 static final int DY[] = {-1,1,0,0};
 static final int DX[] = {0,0,-1,1};
 static int groupIndex = 1;
 static int groupSize[];
 static int group[][];
 static int map[][];
 
 public static void main(String[]args) throws Exception{
 
 Scanner sc = new Scanner(System.in);
 int N = sc.nextInt();
 int M = sc.nextInt();
 map = new int[N][M]; 
 group = new int[N][M]; 
 groupSize = new int[N*M+1];
 for(int i=0; i<N; i++){
 for(int j=0; j<M; j++)
 map[i][j] = sc.nextInt();
 }
 System.out.println(solve(N,M));
 }
 
 static int solve(int N, int M){
 int max = 0;
 for(int i=0; i<N; i++){
 for(int j=0; j<M; j++){
 if(map[i][j] == 0){ 
 //상하좌우 그룹의 값을 더함
 int size = 1; //0->1로 바꿔주기 때문에 1로 해야함.
 boolean groupCheck[] = new boolean[N*M+1]; 
 for(int k=0; k<4; k++){
 int y = i + DY[k];
 int x = j + DX[k];
 if(y < 0 || x < 0 || y >= N || x >= M)
 continue;
 //이미 해당 그룹 값을 더해주었거나 주위에 있는 요소가 그룹요소가 아님
 if(map[y][x] == 0 || groupCheck[group[y][x]])
 continue;
 //그룹 사이즈를 이전에 구한적이 없음
 if(groupSize[group[y][x]] == 0){
 boolean check[][] = new boolean[N][M];
 check[y][x] = true;
 group[y][x] = groupIndex;
 groupSize[groupIndex] = getGroupSize(N,M,y,x,check) + 1;
 size += groupSize[groupIndex];
 
 groupCheck[group[y][x]] = true;
 groupIndex++;
 }
 else{
 //이미 이전에 구한적이 있음.
 size += groupSize[group[y][x]];
 groupCheck[group[y][x]] = true;
 }
 }
 max = Math.max(max, size); 
 }
 }
 }
 return max;
 }
 static int getGroupSize(int N, int M, int y, int x, boolean check[][]){
 int size = 0;
 for(int i=0; i<4; i++){
 int ny = y + DY[i];
 int nx = x + DX[i];
 if(ny < 0 || nx < 0 || ny >= N || nx >= M || check[ny][nx] || map[ny][nx] == 0)
 continue;
 
 check[ny][nx] = true;
 group[ny][nx] = groupIndex;
 size += getGroupSize(N, M, ny, nx, check) + 1;
 
 }
 return size;
 }
}

gkdud583 4년 전 2

상하좌우의 그룹 값을 더해줄 때 중복을 피하기 위해 boolean groupCheck[][]를 사용하였는데 이 코드는 1000001번의 연산이 발생하고 이를 이중 포문 안에서 사용해서 시간 초과가 나온 것 같습니다. 그룹 중복 체크하는 부분을 HashSet으로 바꿔줘서 맞았습니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC