글 읽기 - 시간초과가 나는 이유를 알려주세요

doryeongpark 5년 전 0

Step 1. BFS로 각 섬들에 번호를 매긴다.

Step 2. Brute Force로 두 지역을 선택하여(물가와 닿아있는지 체크, 서로 다른대륙인지 체크) BFS를 돌려 최단거리 저장

Step 3. 저장된 총 최단거리중에 가장 작은 것을 선택한다.

이런식으로 생각하고 짰습니다. 시간초과가 뜨는데 어떻게하면 해결할 수 있을까요?

import java.util.*;

public class Main {
	
	public static class Position{
		int x; 
		int y;
		public Position(int x, int y){
			this.x = x; this.y = y;
		}
		public boolean equals(Position another){
			return this.x == another.x && this.y == another.y;
		}
		public boolean equals(int x, int y){
			return this.x == x && this.y == y;
		}
		
	}
	
	public static int[] offsetX = {0, 0, 1, -1};
	public static int[] offsetY = {1, -1, 0, 0};
	
	public static int col;
	public static int row;
	
	public static int[][] field;
	public static int[][] dField;
	public static boolean[][] visited;
	
	public static LinkedList<Position> queue = new LinkedList<Position>();
	
	public static int islandCnt = 0;
	
	public static Position dst;
	
	public static ArrayList<Integer> results = new ArrayList<Integer>();
	public static int result = 0;
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		col = sc.nextInt();
		row = col;
		
		field = new int[col][row];
		dField = new int[col][row];
		visited = new boolean[col][row];
		
		for(int y = 0; y < col; ++y){
			for(int x = 0; x < row; ++x){
				field[y][x] = sc.nextInt();
			}
		}
		for(int y = 0; y < col; ++y){
			Arrays.fill(dField[y], 0);
		}

		distinctIslands();
		
		resetVisited();
		queue.clear();
		
		pickSpots(new Stack<Position>(), 2);
		
		int min = Integer.MAX_VALUE;
		for(int result : results){
			if(result < min){
				min = result;
			}
		}
		System.out.println(min);
	}
	
	public static void distinctIslands(){
		
		for(int y = 0; y < col; ++y){
			for(int x = 0; x < row; ++x){
				if(visited[y][x]){continue;}
				if(field[y][x] == 0){continue;}
				queue.addFirst(new Position(x, y));
				visited[y][x] = true;
				++islandCnt;
				dField[y][x] = islandCnt;
				bfs1();
			}
		}
		
	}
	
	public static void bfs1(){
		
		if(queue.isEmpty()){return;}
		int qSize = queue.size();
		for(int i = 0; i < qSize; ++i){
			Position pos = queue.getLast();
			for(int j = 0; j < offsetX.length; ++j){
				int newX = pos.x + offsetX[j];
				int newY = pos.y + offsetY[j];
				if(newX < 0 || newX >= row){continue;}
				if(newY < 0 || newY >= col){continue;}
				if(visited[newY][newX]){continue;}
				if(field[newY][newX] != 1){continue;}
				queue.addFirst(new Position(newX, newY));
				visited[newY][newX] = true;
				dField[newY][newX] = islandCnt;
			}
			queue.removeLast();
		}
		bfs1();

	}
	
	public static void pickSpots(Stack<Position> picked, int cnt){
		
		if(cnt == 0){return;}
		for(int y = 0; y < col; ++y){
			for(int x = 0; x < row; ++x){
				if(dField[y][x] == 0){continue;}
				if(cnt == 2){
					picked.add(new Position(x, y));
				}
				if(cnt == 1){
					dst = new Position(x, y);
					Position src = picked.get(0);
					if(isIsolated(dst) || isIsolated(src)){continue;}
					if(dst.equals(src)){continue;}
					if(dField[src.y][src.x] == dField[dst.y][dst.x]){continue;}
					picked.add(dst);
					queue.clear(); result = 0;
					resetVisited();
					queue.addFirst(src);
					visited[src.y][src.x] = true;
					bfs2();
				}
				pickSpots(picked, cnt - 1);
				picked.pop();
			}
		}
		
	}
	
	public static void bfs2(){
		
		if(queue.isEmpty()){return;}
		int qSize = queue.size();
		++result;
		for(int i = 0; i < qSize; ++i){
			Position std = queue.getLast();
			for(int j = 0; j < offsetX.length; ++j){
				int newX = std.x + offsetX[j];
				int newY = std.y + offsetY[j];
				if(newX < 0 || newX >= row){continue;}
				if(newY < 0 || newY >= col){continue;}
				if(dst.equals(newX, newY)){
					results.add(result - 1);
					return;
				}
				if(visited[newY][newX]){continue;}
				if(dField[newY][newX] != 0){continue;}
				queue.addFirst(new Position(newX, newY));
				visited[newY][newX] = true;
			}
			queue.removeLast();
		}
		bfs2();
		
	}
	
	public static void resetVisited(){
		
		for(int y = 0; y < col; ++y){
			Arrays.fill(visited[y], false);
		}
		
	}
	
	public static boolean isIsolated(Position pos){
		
		for(int i = 0; i < offsetX.length; ++i){
			int newX = pos.x + offsetX[i];
			int newY = pos.y + offsetY[i];
			if(newX < 0 || newX >= row){continue;}
			if(newY < 0 || newY >= col){continue;}
			if(dField[newY][newX] == 0){return false;}
		}
		return true;
		
	}
}

djm03178 5년 전 1

대략적인 시간복잡도를 분석해 보면,

두 지점을 뽑는 경우의 수: O((RC)^2) ~= 1억
각 경우마다 BFS: O(RC) ~= 1만

곱하면 1조 정도가 되고, 실제로는 상수가 매우 작을 것이므로 이보다는 작지만, 여전히 5초 안에 들어오기에는 무리일 것입니다.

이렇게 바꿔보세요. 한 지점을 뽑고, 그 지점에서 BFS를 수행하면 가장 먼저 닿는 다른 섬이 어디인지는 자연스럽게 알아낼 수 있습니다. 굳이 그 종착점이 어디인지까지 정해놓고 BFS를 할 필요가 있을까요?

doryeongpark 5년 전 0

답변 감사드립니다. 참고해서 다시 짜볼게요!

ine 2년 전 0

감사합니다. 조언해주신대로 코드 고쳤더니 통과했네요!

배우고 갑니다.

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

문제

문제

출처

ICPC

시간초과가 나는 이유를 알려주세요

doryeongpark 5년 전 0

djm03178 5년 전 1

doryeongpark 5년 전 0

ine 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말