다리 만들기 2(BJ_G1_17472)

1. 문제 링크

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

---

 

2. 나의 코드

메모리: 14352kb
시간: 128ms
코드 길이: 5993B
시간 복잡도 : O(섬의갯수^2).
설명:먼저 DFS를 통해서 섬의 갯수를 알고, 섬의 번호를 부여한다. 그리고 조합 알고리즘을 사용하여
섬들간의 경우의 수를 구하고 BFS를 사용해서 섬들간의 최소거리를 구한다. 마지막으로 크루스칼 
알고리즘을 사용하여 최소 간선의 합을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Edge implements Comparable<Edge> {
        int from, to, dist;

        public Edge(int from, int to, int dist) {
            super();
            this.from = from;
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.dist, o.dist);
        }

        @Override
        public String toString() {
            return "Edge [from=" + from + ", to=" + to + ", dist=" + dist + "]";
        }
    }

    static class Pos {
        int x, y, d, preD;

        public Pos(int x, int y, int d, int preD) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.preD = preD;
        }

        @Override
        public String toString() {
            return "Pos [x=" + x + ", y=" + y + ", d=" + d + ", preD=" + preD + "]";
        }
    }

    static int N, M, islandCnt;
    static boolean[][] visited;
    static int[][] map;
    static Edge[] edge;
    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };
    static int[] input, parents;
    static List<Edge> edgeList;

    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        edgeList = new ArrayList<>();
        input = new int[2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    ++islandCnt;
                    dfs(i, j);
                }
            }
        }

        comb(0, 1);

        if (islandCnt - 1 > edgeList.size()) {
            System.out.println(-1);
            return;
        }

        parents = new int[islandCnt + 1];
        Collections.sort(edgeList);

        make();

        long ans = 0;
        int cnt = 0;
        for (Edge edge : edgeList) {
            if (!union(edge.from, edge.to)) {
                continue;
            }
            ans += edge.dist;
            if (++cnt == islandCnt - 1) {
                break;
            }
        }
        for (int i = 1; i < islandCnt - 1; i++) {
            if (find(i) != find(i + 1)) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans);
    }

    private static void make() {
        for (int i = 0; i < islandCnt + 1; i++) {
            parents[i] = i;
        }
    }

    private static int find(int a) {
        if (parents[a] == a)
            return a;
        return parents[a] = find(parents[a]);
    }

    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot)
            return false;
        parents[bRoot] = aRoot;
        return true;
    }

    // 섬의 갯수 세기, 섬의 인덱스 바꾸기
    private static void dfs(int x, int y) {
        visited[x][y] = true;
        map[x][y] = islandCnt;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(nx, ny) && map[nx][ny] != 0 && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }

    // 각각의 섬들 간의 거리를 리스트에 추가
    private static int bfs(int x, int y, int target) {
        Queue<Pos> q = new LinkedList<>();
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(nx, ny) && !visited[nx][ny] && (map[nx][ny] == 0 || map[nx][ny] == target)) {
                q.offer(new Pos(nx, ny, 1, i));
                visited[nx][ny] = true;
            }
        }

        while (!q.isEmpty()) {
            Pos now = q.poll();
            if (map[now.x][now.y] == target && now.d > 2)
                return now.d - 1;
            else if (map[now.x][now.y] == target && now.d <= 2) {
                continue;
            }
            int nx = now.x + dx[now.preD];
            int ny = now.y + dy[now.preD];

            if (isValid(nx, ny) && !visited[nx][ny] && (map[nx][ny] == 0 || map[nx][ny] == target)) {
                q.offer(new Pos(nx, ny, now.d + 1, now.preD));
                visited[nx][ny] = true;
            }
        }
        return -1; // 못찾을 경우
    }

    // 섬들간의 연결 조합 만들기
    private static void comb(int cnt, int start) {
        if (cnt == 2) {
            int minDist = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == input[0]) {
                        visited = new boolean[N][M];
                        int result = bfs(i, j, input[1]);
                        if (result != -1 && result > 1) {
                            minDist = Math.min(minDist, result);
                        }
                    }
                }
            }
            if (minDist != Integer.MAX_VALUE && minDist > 1)
                edgeList.add(new Edge(input[0], input[1], minDist));
            return;
        }
        for (int i = start; i <= islandCnt; i++) {
            input[cnt] = i;
            comb(cnt + 1, i + 1);
        }
    }

    // 맵 밖으로 나가는 지 확인
    private static boolean isValid(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}

 

---

 

3. 정답 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static class Node implements Comparable<Node>{
		int to;
		int from;
		int value;
		
		public Node(int to, int from, int value) {
			this.to = to;
			this.from = from;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
		
	}

	static int n,m, islandCnt;
	static int[][] map;
	static int[] parents;
	static Queue<int[]> q;
	static PriorityQueue<Node> pq = new PriorityQueue<>(); ;
	static boolean[][] check;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	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());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		islandCnt =2;
		check = new boolean[n][m];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]==1 && !check[i][j]) {
					islandIndexing(j, i, islandCnt);
					islandCnt++;
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]!=0) {
					makeBridge(j, i, map[i][j]);
				}
			}
		}
		
		islandCnt--;
		parents = new int[islandCnt];
		for(int i=1; i<islandCnt; i++) {
			parents[i] = i;
		} 
		int answer = shortestPath();
		System.out.println(answer == 0 ? -1 : answer);
		
	}
	
	// 1번 로직 (그래프 색칠) 
	static void islandIndexing(int x, int y, int idx) {
		q = new LinkedList<>();
		
		
		q.add(new int[] {x,y});
		map[y][x] = idx;
		check[y][x] = true;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px = p[0];
			int py = p[1];
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx<0 || ny <0 || nx > m-1 || ny > n-1 || check[ny][nx]) continue;
				
				if(map[ny][nx]==1) {
					map[ny][nx] = idx;
					check[ny][nx] = true;
					q.add(new int[] {nx,ny});
				}
			}
		}
	}
    
	// 2번 로직 (그래프 연결) 
	static void makeBridge(int x, int y, int idx) {
		q = new LinkedList<>();	
		check = new boolean[n][m];
		for(int d=0; d<4; d++) {
			q.add(new int[] {x,y,0});
			check[y][x] = true;
			
			while(!q.isEmpty()) {
				int[] p = q.poll();
				int px = p[0];
				int py = p[1];
				int move = p[2];
				
				int nx = px + dx[d];
				int ny = py + dy[d];
				
				if(nx<0 || ny <0 || nx > m-1 || ny > n-1 || check[ny][nx]) continue;
				
				if(map[ny][nx]!=idx) {
					if(map[ny][nx] !=0) {
						int from = idx-1;
						int to = map[ny][nx]-1;
						int bridgeLen = move;
						if(bridgeLen>1) {		
							pq.add(new Node(from, to, bridgeLen));
							break;
						}
					}else {
						check[ny][nx] = true;
						q.add(new int[] {nx, ny, move+1});
					}
				}
			}
			q.clear();
		}
	}

	// 3번 로직 (최소 신장트리 -크루스칼) 
	static int shortestPath() {
		int sum =0;
		int size = pq.size();
		for(int i=0; i< size; i++) {
			Node node = pq.poll();
			int x = node.from;
			int y = node.to;
			
			if(find(x) != find(y)) {
				sum += node.value;
				union(x,y);
			}
		}
		
		int rx = parents[1];
		for(int i=2; i<islandCnt; i++) {
			if(rx != find(parents[i])) {
				// System.out.println("연결 x ");
				return 0;
			}
		}
		
		return sum;
	}
	
	
	static int find(int x) {
		if(parents[x] == x) return x;
		int rx = find(parents[x]);
		return rx;
		
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x<y) {
			parents[y]=x;
		}
		else {
			parents[x] =y;
		}
	}
}

 

---

 

4. 배운 점

- 문제를 잘 읽자. 섬들을 모두 이어야 하는데 그 부분을 처리하지 않아 몇시간을 낭비했다.

- 여러가지 알고리즘을 사용하는 문제가 많다. 항상 코딩하기 전 설계를 하고 테스트를 해보자