[백준/JAVA] 17472번: 다리 만들기 2

🔺 문제

17472번: 다리 만들기 2

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {-1, 0, 1, 0};    // 상하 이동 (dy)
    static int[] dc = {0, 1, 0, -1};    // 우좌 이동 (dx)
 
    static int[][] map; 
    static int[] parent;
    static int N, M, sNum; 
    static boolean[][] visited;   // BFS 위한 방문 정보 저장 배열
    
    static ArrayList<ArrayList<int[]>> sumList; // 모든 섬 정보 저장
    static ArrayList<int[]> mlist;              // 1개의 섬 정보 저장
    
    static PriorityQueue<Edge> pq; // 다리 정보 저장
    
    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());   // 세로
        
        pq = new PriorityQueue<>();
        
        // 맵 정보 저장
        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()); 
            }
        }
        
        // 1. BFS 탐색 통해 섬 분리
        sNum = 1;   // 섬 인덱스
        sumList = new ArrayList<>();
        visited = new boolean[N][M];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                // 바다 X && 방문 X일 때 같은 섬으로 인식
                if(map[i][j] != 0 && !visited[i][j]) {
                    BFS(i, j);
                    sNum++;
                    sumList.add(mlist);
                }
            }
        }
        
        // 2. 섬의 각 지점에서 만들 수 있는 모든 에지 저장
        for(int i = 0 ; i < sumList.size() ; i++) {
            ArrayList<int[]> now = sumList.get(i);  // 1개의 섬 정보
            
            for(int j = 0 ; j < now.size() ; j++) {
                // 1개의 섬의 모든 위치에서 만들 수 있는 다리 정보 저장
                int r = now.get(j)[0];
                int c = now.get(j)[1];
                int now_S = map[r][c];
                
                // 상하좌우 검색
                for(int d = 0 ; d < 4 ; d++) {
                    int tmpR = dr[d];
                    int tmpC = dc[d];
                    int len = 0;
                    
                    while(r + tmpR >= 0 && r + tmpR < N && c + tmpC >= 0 && c + tmpC < M) {
                        // 같은 섬이면 에지 생성 불가
                        if(map[r + tmpR][c + tmpC] == now_S)
                            break;
                        // 같은 섬도 아니고 바다도 아니면 다른 섬
                        else if(map[r + tmpR][c + tmpC] != 0) {
                            if(len >= 2) {
                                pq.add(new Edge(now_S, map[r + tmpR][c + tmpC], len));
                            }
                            break;
                        }
                        // 바다면 다리 길이 연장
                        else {
                            len++;
                        }
                        
                        if(tmpR < 0) tmpR--;
                        else if(tmpR > 0) tmpR++;
                        else if(tmpC < 0) tmpC--;
                        else if(tmpC > 0) tmpC++;
                    }
                }
            }
        }
        
        // 부모 노드 배열 채우기
        parent = new int[sNum];
        for(int i = 0 ; i < parent.length ; i++) {
            parent[i] = i;
        }
        
        // 3. 최소 신장 트리 - 크루스칼
        int useEdge = 0;    // 사용된 에지 수
        int answer = 0;
        
        while(!pq.isEmpty()) {
            Edge now = pq.poll();   // 큐에서 에지 정보 가져오기
            
            // 같은 부모가 아니라면 사이클 없으므로 연결
            if(find(now.s) != find(now.e)) {    
                union(now.s, now.e);
                answer += now.v;
                useEdge++;
            }
        }
        
        // 사용된 에지 개수 = 노드 개수 - 1이면 알고리즘 종료
        if(useEdge == sNum - 2) System.out.println(answer);
        else                    System.out.println(-1);
    }
    
    // 유니온파인드
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    public static int find(int a) {
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }
    
    // BFS 이용해 연결된 섬 탐색
    public static void BFS(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        mlist = new ArrayList<>();
        
        int[] start = {i, j};
        q.add(start);
        mlist.add(start);
        visited[i][j] = true;
        map[i][j] = sNum;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            int r = now[0];
            int c = now[1];
            
            // 상하좌우 탐색
            for(int d = 0 ; d < 4 ; d++) {
                int tmpR = dr[d];
                int tmpC = dc[d];
                
                // 🔔 현재 위치에서 상하좌우로 이동하면서 같은 섬 탐색하기 위해 while문 사용
                while(r + tmpR >= 0 && r + tmpR < N && c + tmpC >= 0 && c + tmpC < M) {
                    // 방문 X & 바다X면 같은 섬 취급
                    if(visited[r + tmpR][c + tmpC] == false && map[r + tmpR][c + tmpC] != 0) {
                        addNode(r + tmpR, c + tmpC, q);
                    } else break;
                    
                    if(tmpR < 0)      tmpR--;
                    else if(tmpR > 0) tmpR++;
                    else if(tmpC < 0) tmpC--;
                    else if(tmpC > 0) tmpC++; 
                }
            }
        }
    }
    
    // 특정 위치를 섬의 정보로 넣는 함수
    private static void addNode(int i, int j, Queue<int[]> queue) {
        map[i][j] = sNum;
        visited[i][j] = true;
        int[] tmp = {i, j};
        mlist.add(tmp);
        queue.add(tmp);
    }
 
}
 
class Edge implements Comparable<Edge> {
    int s, e, v;
    
    Edge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    
    // 가중치 오름차순 정렬
    @Override
    public int compareTo(Edge p) {
        return this.v - p.v;
    }
}

✅ 해결 아이디어
✔ 최소 신장 트리 (MST) &  BFS
1) 지도 정보를 2차원 배열에 저장 & 섬으로 표시된 모든 섬에서 BFS 수행해 섬 구분 (상하좌우 방향 탐색)
   → 방문 X & 바다 X 일 때 같은 섬으로 인식
2) 상하좌우 탐색하며, 연결할 곳이 바다라면 계속 탐색. 다른 섬 만났을 때 다리 길이가 2 이상이면 에지 리스트에 다리 추가
3) 모든 에지 가중치 기준 오름차순 정렬해 MST 수행

 

---

🔺 다른 풀이들

- 깔끔한 설명 풀이...👍👍👍👍👍

[BOJ] 백준 17472번 다리 만들기 2 (Java)

 

[백준]17472: 다리 만들기 2 - JAVA

[Java][자바][백준][17472번] 다리 만들기2

 

 

- 자동 정렬을 위해 우선순위 큐를 사용하시지 않고 이렇게 정렬하셨다.

[백준 Gold 2] 17472 다리 만들기 2 - Java

Collections.sort(bridge, (a, b) -> {
    return a[2] - b[2];
});

 

 

- 신기하다 DFS 사용하셨다 (참고용)

[Java] 백준 17472번 : 다리 만들기 2

 

 

- 프림 알고리즘을 사용하셨다.

로그인

---

💬 느낀 점

어렵구만... 2차원 ArrayList는 난생 첨 봐서 또 헉...하면서 봤다...

다른 분들 풀이를 보니 어렵게 2차원 ArrayList까지는 쓸 필요가 없는 것 같다.💦💦

ArrayList<ArrayList<int[]>> sumList; 

 

그리고 집중을 안 하면.. 흐름을 놓치기 쉬운 문제인듯하다...

집중력을 상승시켜보좌,,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V	6/27

 

 

(+6/27 2회독)

아래 블로그 참고해서 작성했다...개인적으로 첫 번째 풀이보다 이게 더 이해하기 나은 느낌이었다.

 

[ny][nx]처럼 [y][x] 순서로 접근하는 이유는,

배열의 행과 열이 주어진 좌표(x,y)와 반대로 매핑되어있기 때문이다.

[BOJ] 백준 17472번 다리 만들기 2 (Java)

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    static int n,m, islandCnt;
    static int[][] map;
    static int[] parents;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    
    // bfs용
    static Queue<int[]> q;
    static boolean[][] check;
    
    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;  // 2인 이유 : 0은 바다 , 1은 이미 방문한 섬 나타내므로
        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]) {
                    bfs(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--;    // 배열 인덱스와 섬 번호 맞추기 위해 1 빼는 것
        parents = new int[islandCnt + 1];
        for(int i = 1; i <= islandCnt; i++) {
            parents[i] = i;
        } 
        int answer = shortestPath();
        System.out.println(answer == 0 ? -1 : answer);
        
    }
    
    // 1번 로직 (그래프 색칠) 
    static void bfs(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();
            
            for(int i=0; i<4; i++) {
                int nx = p[0] + dx[i];
                int ny = p[1] + 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 move = p[2];
                
                int nx = p[0] + dx[d];
                int ny = p[1] + 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;         // 현재 섬 번호 - 1
                        int to = map[ny][nx] - 1;   // 인접한 다른 섬 번호 - 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();
            
            if(find(node.s) != find(node.e)) {
                sum += node.v;
                union(node.s, node.e);
            }
        }
    
        for(int i = 2; i<islandCnt; i++) {
            if(parents[1] != 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;
        }
    }
    
    static class Node implements Comparable<Node>{
        int s, e, v;
        
        public Node(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.v - o.v;
        }
        
    }
}

---

(참고)

✔ 2차원 ArrayList : ArrayList< ArrayList<int[]> > - 각 요소는 int[] 배열을 포함하는 ArrayList

→ ArrayList의 첫 번째 요소 : ArrayList<int[]>

→ 위 요소의 첫 번째 요소 : int[] 배열

ArrayList<ArrayList<int[]>> list = new ArrayList<>();
ArrayList<int[]> sublist1 = new ArrayList<>();
int[] arr1 = {1, 2};
int[] arr2 = {3, 4};
sublist1.add(arr1);
sublist1.add(arr2);
list.add(sublist1);

ArrayList<int[]> sublist2 = new ArrayList<>();
int[] arr3 = {5, 6};
sublist2.add(arr3);
list.add(sublist2);

System.out.println(list.get(0).get(0)[0]); // 1
System.out.println(list.get(0).get(1)[1]); // 4
System.out.println(list.get(1).get(0)[0]); // 5