글 읽기 - 2146 다리만들기 시간초과 부탁드립니다

bbangssi91 5년 전 0

먼저 문제 접근방법부터 말씀드리도록 하겠습니다.

LinkedList<LinkedList<Info>> territoryList; 로 선언하여

대륙의 개수는 territoryList이고, 그 안에 포함된 대륙의 좌표는 listInfo 라는 이름의 list로 넣어주었습니다.

1) divideContinent() 메소드에서 BFS를 사용하여 처음 육지인 곳부터 확장을 시작합니다.

-> 확장을 최대한 한 다음에 1번 대륙에 해당하는 모든 좌표를 territoryList의 0번 인덱스에 넣어줍니다.

-> 마찬가지로 for문 루프를 계속 돌면서 2번 대륙 -> 1번 인덱스 / 3번 대륙 -> 2번 인덱스 / ~~~ 반복

2) 그다음 makePair() 메소드에서 1 ~ N개의 대륙을 2개의 조합 경우의 수를 찾기 위해 DFS로 구현하였습니다.

3) 다음 calcDist() 메소드에서 거리를 계산하고 최소 값을 갱신합니다.

예를들면 총 대륙의 개수는 3개이고 1번 2번 대륙을 골랐을 때,

1번 대륙 (0, 0) (0, 1) (0,2) (0,3)

2번 대륙 (4, 4) (5, 4) (4, 3)

의 상태로 거리를 계산하면 최소 값은 4가 되어 return을 합니다.

시간초과를 줄이려면 어떤 부분을 수정해야될지 도움주시면 감사하겠습니다ㅜㅜ

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

public class Boj2146 {

	static int N;
	static int map[][];
	static final int dy[] = {-1, 0, 1, 0};
	static final int dx[] = {0, 1, 0, -1};
	static LinkedList<LinkedList<Info>> territoryList;
	static int result = Integer.MAX_VALUE;
	static boolean visited[][]; 
	static class Info{
		int row;
		int col;
		public Info(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0;j < N; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		territoryList = new LinkedList<LinkedList<Info>>();
		
		//1. 대륙을 나눠본다.
		divideContinent();
		
		boolean choose[] = new boolean[territoryList.size()];
        
		//2. 0~N개의 대륙 중 2개를 짝 짓어본다
		for(int i = 0; i < territoryList.size(); i++){
			choose[i] = true;
			makePair(i, 1, choose);
			choose[i] = false;
		}
		
		//debug();
		if(territoryList.size() == 1) System.out.println(0);
		else{
			System.out.println(result-1);			
		}
		
		br.close();
	}//end main
	
	private static void divideContinent() {
		Queue<Info> q = new LinkedList<>();
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(map[i][j] == 1 && !visited[i][j]){
					LinkedList<Info> listInfo = new LinkedList<>();
					q.add(new Info(i, j));
					visited[i][j] = true;
					listInfo.add(new Info(i, j));
					
					while(!q.isEmpty()){
						Info info = q.poll();
						
						for(int dir = 0; dir < 4; dir++){
							int nextRow = info.row + dy[dir];
							int nextCol = info.col + dx[dir];
							
							if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
							if(visited[nextRow][nextCol]) continue;
							if(map[nextRow][nextCol] == 0) continue;
							
							visited[nextRow][nextCol] = true;
							listInfo.add(new Info(nextRow, nextCol));
							q.add(new Info(nextRow, nextCol));
						}
					}
					if(listInfo.size() != 0){
						territoryList.add(new LinkedList<>(listInfo));						
					}
					//test();
				}
			}
		}
			
	}//end divideContinent()	
	
	
	private static void makePair(int index, int count, boolean[] choose) {
		//1. 2개 짝짓어지면 거리 계산하고 정답 갱신
		if(count == 2){
			result = Math.min(result, calcDist(choose));
			return;
		}
		
		for(int i = index + 1; i < territoryList.size(); i++){
			choose[i] = true;
			makePair(i, count+1, choose);
			choose[i] = false;
		}
		
		
		
	}//end makePair()
	
	private static int calcDist(boolean[] choose) {
		int minNum = 9999;
		
		int first = 999;
		int second = 999;
		
		for(int i = 0; i < choose.length; i++){
			if(choose[i]){
				if(first == 999){
					first = i;
				}else{
					second = i;
				}
			}
		}
				
		int firstSize = territoryList.get(first).size();
		int secondSize = territoryList.get(second).size();
		
		for(int i = 0; i < firstSize; i++){
			Info firstPos = territoryList.get(first).get(i);
			for(int j = 0; j < secondSize; j++){
				Info secondPos = territoryList.get(second).get(j);
				int min = Math.abs((firstPos.row - secondPos.row)) + Math.abs(firstPos.col - secondPos.col);
				minNum = Math.min(minNum, min);

			}
		}
		
		return minNum;
	}

}//end class

djm03178 5년 전 2

첫째로, 링크드 리스트에서 임의의 i번째 원소를 얻어오는 것은 i에 비례하는 시간이 걸립니다. 링크드 리스트의 구조에 대해 알아보세요. i번째 원소를 곧바로 얻어오려면 LinkedList 대신에 ArrayList를 써야 합니다.

둘째로, calcDist 메서드에서 choose의 길이만큼을 보면서 골라진 2개를 다시 체크하고 있는데, 이러면 최악의 경우 다음과 같이 됩니다. 100x100 크기의 맵에 체스판 모양으로 섬이 5000개 있다면, 5000개 중 2개를 뽑는 경우의 수 약 2500만 개마다 5000개의 섬을 체크해서 골라진 2개의 섬을 뽑아내야 하므로 약 1250억 번의 체크가 수행됩니다. 이렇게 하지 말고, 고른 섬 2개의 번호를 직접 calcDist에 보낼 수 있게 해보세요.

bbangssi91 5년 전 1

와.. 정말 감사합니다 덕분에 문제해결했습니다.

저는 choose의 길이만큼 한번만 for문을 돌려서 O(N)이니 크게 문제없겠다라고 생각했었는데

2개 뽑는 경우의 수만큼을 생각못했었네요 감사합니다 많이 배워갑니다!!

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

문제

문제

출처

ICPC

2146 다리만들기 시간초과 부탁드립니다

bbangssi91 5년 전 0

djm03178 5년 전 2

bbangssi91 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말