글 읽기 - java bfs 79% 시간 초과

shchon1993 4년 전 0

최대한 코드를 최적화하였다고 생각합니다. 78~79%에서 계속 시간초과가 발생하는데 어느 부분에서 시간초과가 발생하는 걸까요?

package 삼성;
import java.util.*;
public class N16234_temp {

	static int N;
	static int L;
	static int R;
	
	static int map[][];
	static int map_temp[][];
	static int map2[][];
	
	static int nextCnt;
	static int cnt; // 인구합병횟수
	
	static int result = 0;
	static int result_cnt = 0;
	
	
	static Queue que = new LinkedList<>();

	static boolean visited[][];

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner  sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[N][N];
		map_temp = new int[N][N];
		

		visited = new boolean[N][N];

		
		for(int i = 0; i<N; i++)
		{
			for(int j = 0; j<N; j++) {
				map[i][j] = sc.nextInt();
				map_temp[i][j] = map[i][j];
				
			}
		}
		
		while(true)
		{
			for(int i = 0; i<N; i++)
			{
				for(int j = 0; j<N; j++)
				{
					if(!visited[i][j])
					{
						bfs(i,j);
						visited = new boolean[N][N];						
						result = 0;
						result_cnt = 0;
					}
				}
			}
			
			if(nextCnt==0)
				break;
			nextCnt = 0;
			cnt++;
			copy();
			
			
			visited = new boolean[N][N];
			
		}
		
		System.out.println(cnt);
		
		
	}
	
	public static void bfs(int x , int y)
	{
		int dx[] = {0,1,0,-1};
		int dy[] = {1,0,-1,0};
		//         동 서 남 북

		que.add(new human1(x,y));
		result += map[x][y];
		result_cnt++;
		visited[x][y] = true;
		human1 hm;
	
		while(!que.isEmpty())
		{
			hm = (human1)que.poll();
			
			
			
			
			for(int d = 0; d<4; d++)
			{
				int dxx = hm.x + dx[d];
				int dyy = hm.y + dy[d];
				
				
				if(dxx>=0 && dyy >= 0 && dxx<N && dyy<N)//맵 범위 내인가?
				{
					if(!visited[dxx][dyy])//방문하지 않았는가?
					{
						if(check(hm.x, hm.y, dxx, dyy))//인구이동이 가능한가?
						{	
							
							visited[dxx][dyy] = true;
							que.add(new human1(dxx,dyy));
							result += map[dxx][dyy];
							result_cnt++;
						}
					}
				}
			}
			
		}
		
		mapChange();	
		
		
		
	}
	
	public static boolean check(int bx,int by, int ax, int ay)
	{
		int result  = Math.abs(map[bx][by] - map[ax][ay]);
		
		if(result >= L && result <= R)
			return true;
		else
			return false;
	}
	public static void mapChange()
	{
	
		//System.out.println(result +" " + result_cnt);
		result /= result_cnt;
		
		
		if(result_cnt>1)
		{
		for(int i = 0; i<N; i++)
		{
			for(int j = 0; j < N ; j++)
			{
				if(visited[i][j])
					map_temp[i][j] = result;
			}
		}
			
			nextCnt++;
		}
	}
	public static void copy()
	{
		for(int i = 0; i<N; i++)
		{
			for(int j = 0; j<N; j++)
			{
				map[i][j] = map_temp[i][j];
			}
		}
	}


}

class human1{
	int x;
	int y;

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

junhok82 4년 전 1

모든 코드를 보지 않았지만 57번째줄에 visited 배열을 계속 선언을 해줄 이유가 없어보입니다.

junhok82 4년 전 1

그리고 맵을 copy하시는데, 위와 같은 방식으로하면 모든 배열 인덱스를 순회하기때문에 비효율적입니다. ArrayList에 list.add(new int[] {y,x}) 이런식으로 변경된 부분만 체크해서 맵을 변경하시면 될거같아요

junhok82 4년 전 1

위와 같은 맥락으로 "순회할 곳만 순회해야한다"는 시간을 줄이는데 좋은 포인트입니다.

위와 같은 방법으로도 충분히 통과하지만, 더욱 시간을 줄이기 위해서 main함수에서 `모든 배열의 인덱스를 조회`하면서 bfs() 하지말고, bfs() 후 `변경된 부분`에 있어서만 처리하는 것이 많은 시간을 줄여줄겁니다.

shchon1993 4년 전 0

좋은 댓글 감사합니다!

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

문제

문제

출처

ICPC

java bfs 79% 시간 초과

shchon1993 4년 전 0

junhok82 4년 전 1

junhok82 4년 전 1

junhok82 4년 전 1

shchon1993 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말