글 읽기 - 23%에서 24%넘어가면 시간초과라고 뜹니다.

qw2er 6년 전 0

아래와 같은 알고리즘(BFS)을 사용하였는데 시간 초과가 발생하였습니다.

1. 토마토가 새로 익은 경우 리스트에 집어넣고 안 익은 토마토가 존재하는지 검사하였습니다.

2. 토마토가 모두 익은 경우 걸린 날짜를 반환합니다.

3. 1에서 리스트에 넣은 토마토의 주변 토마토를 익었다고 표시합니다.

4. 주변 토마토가 한 개라도 새로 익은 경우 위의 작업을 반복합니다.

5. 3번 과정(주변 토마토를 익었다고 표시하는 과정)에서 새로 익은 토마토가 없는 경우 -1로 막혀 영원히 안 익는 토마토가 있다는 뜻이므로 -1을 반환합니다.

시간을 줄일 수 있는 불필요한 과정이나 구현한 알고리즘 중 틀린 부분을 알려주시면 감사하겠습니다.

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int map[][] = new int[n][m];
        boolean visited[][] = new boolean[n][m];
        
        for(int i = 0; i < n; i++){
        	for(int j = 0; j < m; j++){
        		map[i][j] = sc.nextInt(); 
        	}
        }

		System.out.println(tomato(map, visited, n, m, 0));   
		sc.close();
	}
	
	static int tomato(int[][] map, boolean[][] visited, int n, int m, int count){
		
		boolean end_flag = true;
		ArrayList<int[]> list = new ArrayList<int[]>();
		for(int i = 0; i < n; i++){
        	for(int j = 0; j < m; j++){
        		if(!visited[i][j] && map[i][j] == 1){//새로익은 토마토를 저장
        			int[] point = {i, j};
        			list.add(point);
           		}else if(end_flag && map[i][j] == 0){//안 익은 토마토 검사
        			end_flag = false;
        		}
        	}
        }
		if(end_flag) // 토마토가 모두 익은 경우 종료
			return count;
        
		boolean loop_flag = true;
		for(int[] point: list){
			if(point[0]-1 >= 0 && map[point[0]-1][point[1]] == 0){//왼쪽이 익었는지 검사
				map[point[0]-1][point[1]] = 1;	
				loop_flag = false;
			}
			if(point[1]-1 >= 0 && map[point[0]][point[1]-1] == 0){//위쪽이 익었는지 검사
				map[point[0]][point[1]-1] = 1;
				loop_flag = false;
			}
			if(point[0]+1 < n && map[point[0]+1][point[1]] == 0){//오른쪽이 익었는지 검사
				map[point[0]+1][point[1]] = 1;
				loop_flag = false;
			}
			if(point[1]+1 < m && map[point[0]][point[1]+1] == 0){//아래가 익었는지 검사
				map[point[0]][point[1]+1] = 1;
				loop_flag = false;
			}
			visited[point[0]][point[1]] = true;
		}

		if(loop_flag) // 새로익은 토마토가 없으면 -1반환
			return -1;
		
		return tomato(map, visited, n, m, count + 1);
	}
}

djm03178 6년 전 1

이 알고리즘의 수행 시간을 생각해봅시다.

매 사이클마다 n*m 크기의 배열을 모두 돌면서 새로 익은 토마토들에 대해서 검사를 수행하는군요.

새로 익은 토마토들에 대해서 검사하는 횟수는 어차피 창고의 크기를 넘어가지 않으니, O(nm)으로 문제될 수준이 아닙니다.

그러나, n*m 크기의 배열을 검사하는 횟수가 가장 많은 경우는 마치 소용돌이 모양으로 돌면서 한 줄로만 토마토가 익어나갈 수 있는 상황 같은 걸 생각하면 되는데, 이 경우에는 돌아야 하는 사이클의 횟수가 무려 O(nm)에 육박하고, 매 사이클에 n*m개를 검사해야 하니 시간복잡도는 O(n²m²)이 됩니다.

어떻게 줄여야 할까요? 핵심은, "이전 사이클에 찾은 '새로 익은 토마토'에 대한 정보를 다음 사이클에서 바로 사용한다"입니다. 배열을 일일히 순회할 필요가 없습니다. 어디어디에 새로 익은 토마토가 있는지에 대한 정보를 알고 있으면 됩니다.

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

문제

문제

출처

ICPC

23%에서 24%넘어가면 시간초과라고 뜹니다.

qw2er 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말