글 읽기 - 시간초과가 뜨는 이유를 알고싶습니다.

seokjune96 3년 전 0

이중 for문으로 맵을 보면서 0을 만나면 BFS로 그룹id를 넣어주고 배열에 그룹의 길이를 저장시킨후 출력할때 주변노드의 그룹id를 읽어와서 합하게 풀었는데 왜 시간초과가 뜨는지 모르겠네요 설명해주실수 있는 선배님들 있을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static int[] dY = new int[] {0,-1,0,1};
	private static int[] dX = new int[] {-1,0,1,0};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		//맵을 넣을 배열
		int[][] map = new int[n][m];
		//그룹id를 저장할 배열
		int[][] groupIdmap = new int[n][m];
		//그룹id가 각 갈수있는 최대 길이를 담을 배열
		int[] lengthList = new int[n*m+1];
		
		for(int i=0;i<n;i++) {
			String mapinfo = br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(mapinfo.substring(j, j+1));
			}
		}
		
		
		//전체 배열을 이중for문으로 돌면서 0을 만날때 BFS 돌림
		int groupId = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j] == 1) continue;
				int length = bfs(i,j,n,m,map,groupIdmap,++groupId);
				lengthList[groupId] = length;
			}
		}
		
		//위 작업 끝나면 groupIdmap에는 그룹핑된 인덱스 정보가 있고
		//lengthList에는 각 그룹이 가지고있는 최대 길이 정보가 들어가있게 됨
		//전체 칸 돌면서 1일때 이동할수 있는 칸 출력 0일때는 0출력
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j] == 0) {
					bw.append("0");
					continue;
				}else if(map[i][j]==1) {
					//주변 노드들 탐색해서 주변 노드의 groupid를 해쉬에 삽입
					HashSet<Integer> hash = new HashSet<Integer>();
					for(int k=0;k<4;k++) {
						int nx = i+dX[k];
						int ny = j+dY[k];
						
						if(nx>=0 && ny>=0 && nx<n && ny<m && map[nx][ny]==0 && !hash.contains(groupIdmap[nx][ny])) {
							hash.add(groupIdmap[nx][ny]);
						}

					}
					int sum=1;
					for(int groupid : hash) {
						sum += lengthList[groupid];
					}
					bw.append(Integer.toString(sum%10));
					
				}
			}
			bw.append("\n");
			
		}
		
		bw.flush();
	}
	
	//param:1) 현재 노드의 x행값, 2)현재노드의 열값 3)맵의 전체 행값 4)맵의 전체 열값 5)맵 배열 6)그룹id담을 배열 7)넣은 그룹 id
	//현재 0이 갈수있는 길이의 최대값을 리턴
	private static int bfs(int x, int y, int N, int M, int[][] map, int[][] groupIdmap, int groupId) {
		Queue<Pair> que = new LinkedList<Pair>();
		boolean[][] visited = new boolean[N][M];
		que.add(new Pair(x,y));
		visited[x][y] = true;
		groupIdmap[x][y] = groupId;
		int length=0;
		
		while(!que.isEmpty()) {
			Pair node = que.poll();
			length++;
			
			//주변에 0 있는지 없는지 체크
			for(int i=0;i<4;i++) {
				int nx = node.x+dX[i];
				int ny = node.y+dY[i];
				//맵의 안에 잇고, 0이면서 방문하지 않았으면
				if(nx>=0 && ny>=0 && nx<N && ny<M && map[nx][ny] == 0 && !visited[nx][ny]) {
					que.add(new Pair(nx,ny));
					visited[nx][ny] = true;
					groupIdmap[nx][ny] = groupId;
				}
			}
		}
		return length;
	}
	public static class Pair{
		int x,y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

djm03178 3년 전 1

new boolean[N][M];은 O(NM)의 시간이 걸리고, 이를 bfs할 때마다 수행하므로 최악의 경우 O(NM)번 이 문장이 실행되어 총 O(N^2*M^2) 시간이 걸립니다.

seokjune96 3년 전 0

앗 new boolean[N][M]; 가 시간초과에 걸릴것이라는 생각을 해본적이 없었습니다.

정말 감사합니다. 덕분에 코테 스킬이 하나 늘은 기분이네요

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

문제

문제

출처

ICPC

시간초과가 뜨는 이유를 알고싶습니다.

seokjune96 3년 전 0

djm03178 3년 전 1

seokjune96 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말