백준 #2146 / 다리 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5281	1605	1029	30.035%

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

---

약 한달 전에 풀었다가 계속 틀려서 놔뒀다가 다시 풀었는데 이제는 풀리는구나 ㅠㅠㅜㅠㅠ감격

다른 사람들 푼거 보면 대부분 DFS BFS 섞어서 풀었는데...

나는 좀 다르게 풀었다.

[How To Solve?]

- DFS로 육지를 한 바퀴 쭉 돌아준다.

- 돌면서, 바다와 맞닿아 있는 부분을 island 벡터에 저장하는데, 라벨링과 함께 저장해준다.

- 라벨링이 서로 다른 육지들 간의 좌표값의 차이에 절대값을 씌워준다.

- 대소비교를 통해 가장 작은 값을 MIN에 저장, 출력

예전에 SEA에서 2차원 배열에서 거리를 재는 문제가 있었는데, 두 좌표를 빼고 거기다 -1 해주면 거리가 나온다는 점을 이용.

근데 실행시간이 패망이다...ㅜㅜㅠㅠ 딱 1초 걸려서.. 다른사람들은 0.1초라서 후달리긴 하지만... 실행시간을 더 줄일 수 있는 방법을 생각해야겠다.

+ Contains 쓰려고 일부러 Vector 사용한건데, 안먹히더라... Pair Class를 잘못짜서 그런가??

+ 그래서 그냥 저장된 육지는 2로 바꿨다. 이것마저 안했으면 벡터 엄청 늘어나서 실행시간 더 늘어났을지도..?

[Code]

 

import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Vector;
 
class Pair<K,V>{
    private K Key;
    private V Value;
    public Pair(K Key,V Value) {
        this.Key = Key;
        this.Value = Value;
    }
    public K getKey() {return Key;}
    public V getValue() {return Value;}
    public void setKey(K Key) {this.Key = Key;}
    public void setValue(V Value) {this.Value = Value;}
}
 
class Main {
    
    static int[][] Map;
    static int N,idx;
    static boolean[][] visited;
    static Vector<Pair<Integer,Pair<Integer,Integer>>> island = new Vector<Pair<Integer,Pair<Integer,Integer>>>();
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());
        Map = new int[N][N];
        visited = new boolean[N][N];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++)
                Map[i][j] = stoi(st.nextToken());
        }
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(Map[i][j]==1 && !visited[i][j]) {
                    idx++;
                    dfs(i,j);
                }
            }
        }
        int sz = island.size();
        int MIN = Integer.MAX_VALUE;
        
        for(int i=0;i<sz;i++) {
            int cur_idx = island.get(i).getKey();
            int cur_x = island.get(i).getValue().getKey();
            int cur_y = island.get(i).getValue().getValue();
            for(int j=i+1;j<sz;j++) {
                int next_idx = island.get(j).getKey();
                if(next_idx == cur_idx) continue;
                int next_x = island.get(j).getValue().getKey();
                int next_y = island.get(j).getValue().getValue();
                int result = Math.abs(cur_x-next_x)+Math.abs(cur_y-next_y);
                MIN = MIN > result ? result : MIN;
            }
        }
        System.out.println(MIN-1);
    }
    public static void dfs(int x,int y) {
        if(visited[x][y]) return;
        visited[x][y]=true;
        
        int xx[] = {-1,1,0,0};
        int yy[] = {0,0,-1,1};
        
        for(int i=0;i<4;i++) {
            int nx = x+xx[i];
            int ny = y+yy[i];
            if(nx<0 || ny<0 || nx > N-1 || ny > N-1) continue;
            Pair<Integer,Pair<Integer,Integer>> check = new Pair<>(idx,new Pair(x,y));
            if(Map[nx][ny]==0 && Map[x][y]==1) { 
                Map[x][y]=2;
                island.add(check);
            }
            else if(Map[nx][ny]!=0) dfs(nx,ny);
        }
    }
}