티스토리 뷰

PS/Problem_Solving

[BOJ] 17472.다리 만들기 2(백트래킹, BFS).java

Aaron 2020. 9. 7. 16:39
반응형


#. Problem

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

* The copyright in this matter is in BOJ


#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve


각 섬을 노드, 다리를 가중치가 있는 간선이라고 생각하고

최소 스패닝 트리를 만든다는 생각으로 풀면 된다.


그 말은 즉슨 만들 수 있는 모든 다리(간선)를 우선순위 큐에 넣고 

가중치가 적은 간선부터 선택하며 최소 스패닝 트리를 만들어 나아가면 된다.


최소 스패닝 트리를 만들기 위해

Kruskal, Prim 알고리즘을 사용할 수 있는데, 

간선이 많을 경우 Prim 알고리즘을 사용하는 것이 더 유리할 수 있다.

왜냐하면, Kruskal 은 `간선` 중심, Prim 은 `노드` 중심으로 MST를 만들기 때문에 !

단, 이 가정이 절대적인 것은 아니다. 상황에 따라서 또 달라질 수 있다는 것.


1. 각 섬을 구분하기 위해 섬마다 고유한 번호를 붙여준다.

2. 각 섬들로부터 다리를 설치해보는데, 

   설치한 다리가 다른 섬에 도달한다면 목적 섬까지의 다리 거리를 우선순위 큐에 add

3. 모든 다리의 길이(간선)를 우선순위 큐에 넣었다면,

   Kruskal 혹은 Prim 을 적용하여 해결할 수 있다.


#. Code Using Kruskal


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ17472 {
 
    static int R, C, map[][];
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    static ArrayList<Edge> edgeList;
    static class Edge implements Comparable<Edge> {
        int from, to, dist;
        
        public Edge(int from, int to, int dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.dist, o.dist);
        }
 
    }
    
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); 
            }
        }
        
        // 먼저 각 섬들에게 각기 다른 번호를 부여(2번부터 부여)
        int num = 2;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 육지라면
                if(map[i][j] == 1) {
                    map[i][j] = num;
                    setLandName(i, j, num++);
                }
            }
        }
        
        edgeList = new ArrayList<>();
        // 각 섬들로부터 다리를 설치하는데, 다른 섬이 나오면 그 섬까지의 거리를 우선순위 큐에 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 섬이 아니면 pass
                if(!(map[i][j] >= 2)) continue;
                
                // 섬이면 4방으로 쭉 다리를 놓아보자.
                for (int d = 0; d < 4; d++) {
                    setBridge(i, j, d, map[i][j]);
                }
            }
        }
        
        // 크루스칼 알고리즘 적용
        System.out.println(connectLand(num));
    }
 
    static int[] parents;
    private static int connectLand(int num) {
 
        edgeList.sort(null);
        parents = new int[num];
        
        // Set
        for (int i = 2; i < num; i++) 
            parents[i] = i;
        
        int cnt = 0, res = 0;
        for (Edge edge : edgeList) {
            // 싸이클 형성이 안된다면
            if(union(edge.from, edge.to)) {
                // 섬을 모두 연결
                res += edge.dist;
                // (간선 개수)가 (노드 개수 - 1)개라면 종료
                if(++cnt == (num - 2) - 1) return res;
            }
        }
        
        return -1;
    }
 
    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot == bRoot) return false;
        parents[aRoot] = bRoot;
        return true;
    }
 
    private static int find(int a) {
        if(a == parents[a]) return a;
        return parents[a] = find(parents[a]);
    }
 
    /**
     * 해당 방향(d)으로 다리를 설치해보자.
     * 다리가 다른 섬에 도달하면 목적 섬까지의 다리 길이를 우선순위 큐에 넣기
     * @param r    행 좌표
     * @param c    열 좌표
     * @param d    방향
     * @param here    현재 섬 번호
     */
    private static void setBridge(int r, int c, int d, int here) {
        
        int len = 0;
        
        while(true) {
            r += dr[d];
            c += dc[d];
            // 범위를 벗어나면 out
            if(r < 0 || c < 0 || r >= R || c >= C) return;
            // 같은 섬이에 도달하면 out
            if(map[r][c] == here) return;
            len++;
            // 다른 섬을 만났는데 길이가 2 이상이라면
            if(map[r][c] != here && map[r][c] >= 2) {
                if(len - 1 >= 2) {
                    // 그 섬까지의 다리 길이를 우선순위 큐에 넣기
                    edgeList.add(new Edge(here, map[r][c], len - 1));
                }
                return;
            }
            
        }
    }
 
    /**
     * 연결된 각 섬에 고유한 번호 붙이기
     * @param r    행 좌표
     * @param c    열 좌표
     * @param num    섬 고유 번호
     */
    private static void setLandName(int r, int c, int num) {
        
        // 4방 탐색
        for (int d = 0; d < 4; d++) {
            int rr = r + dr[d];
            int cc = c + dc[d];
            // 범위를 벗어나면 pass
            if(rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
            // 육지가 아닐 경우
            if(map[rr][cc] != 1) continue;
            
            map[rr][cc] = num;
            setLandName(rr, cc, num);
        }
        
    }
 
}
 
cs


#. Code Using Prim


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ17472_prim {
 
    static int R, C, map[][];
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    static ArrayList<Node>[] adj;
    static class Node implements Comparable<Node> {
        int no, dist;
        
        public Node(int no, int dist) {
            this.no = no;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.dist, o.dist);
        }
 
    }
    
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); 
            }
        }
        
        // 먼저 각 섬들에게 각기 다른 번호를 부여(2번부터 부여)
        int num = 2;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 육지라면
                if(map[i][j] == 1) {
                    map[i][j] = num;
                    setLandName(i, j, num++);
                }
            }
        }
        
        adj = new ArrayList[num];
        for (int i = 2; i < num; i++) 
            adj[i] = new ArrayList<>();
        
        // 각 섬들로부터 다리를 설치하는데, 다른 섬이 나오면 그 섬까지의 거리를 우선순위 큐에 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 섬이 아니면 pass
                if(!(map[i][j] >= 2)) continue;
                
                // 섬이면 4방으로 쭉 다리를 놓아보자.
                for (int d = 0; d < 4; d++) {
                    setBridge(i, j, d, map[i][j]);
                }
            }
        }
        
        // 프림 알고리즘 적용
        System.out.println(connectLand(num));
    }
 
    private static int connectLand(int num) {
 
        boolean[] visited = new boolean[num];
        int res = 0;
        int landCnt = 0;
        PriorityQueue<Node> pQ = new PriorityQueue<>();
        // 섬 번호는 2번부터
        pQ.add(new Node(2, 0));
        
        while(!pQ.isEmpty()) {
            Node now = pQ.poll();
            // 이미 확인한 섬
            if(visited[now.no]) continue;
            
            res += now.dist;
            visited[now.no] = true;
            // 모든 섬을 다 확인했다면
            if(++landCnt == (num - 2)) return res;
            
            for (int i = 0; i < adj[now.no].size(); i++) {
                Node next = adj[now.no].get(i);
                // 이미 확인한 섬은 pass
                if(visited[next.no]) continue;
                pQ.add(next);
            }
        }
 
        return -1;
    }
 
    /**
     * 해당 방향(d)으로 다리를 설치해보자.
     * 다리가 다른 섬에 도달하면 목적 섬까지의 다리 길이를 우선순위 큐에 넣기
     * @param r    행 좌표
     * @param c    열 좌표
     * @param d    방향
     * @param here    현재 섬 번호
     */
    private static void setBridge(int r, int c, int d, int here) {
        
        int len = 0;
        
        while(true) {
            r += dr[d];
            c += dc[d];
            // 범위를 벗어나면 out
            if(r < 0 || c < 0 || r >= R || c >= C) return;
            // 같은 섬이면 out
            if(map[r][c] == here) return;
            len++;
            // 다른 섬을 만났는데 길이가 2 이상이라면
            if(map[r][c] != here && map[r][c] >= 2) {
                if(len - 1 >= 2) {
                    // 그 섬까지의 거리를 우선순위 큐에 넣기
                    adj[here].add(new Node(map[r][c], len - 1));
                }
                return;
            }
            
        }
    }
 
    /**
     * 연결된 각 섬에 고유한 번호 붙이기
     * @param r    행 좌표
     * @param c    열 좌표
     * @param num    섬 고유 번호
     */
    private static void setLandName(int r, int c, int num) {
        
        // 4방 탐색
        for (int d = 0; d < 4; d++) {
            int rr = r + dr[d];
            int cc = c + dc[d];
            // 범위를 벗어나면 pass
            if(rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
            // 육지가 아닐 경우
            if(map[rr][cc] != 1) continue;
            
            map[rr][cc] = num;
            setLandName(rr, cc, num);
        }
        
    }
 
}
 
cs




반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[BOJ] 17070.파이프 옮기기 1(DFS).java  (0) 2020.09.09
[SWEA] 2105.디저트 카페.java  (0) 2020.09.07
[BOJ] 17136.색종이 붙이기(백트래킹, 시뮬레이션).java  (0) 2020.09.07
[BOJ] 17471.게리맨더링(부분집합, BFS).java  (0) 2020.09.07
[BOJ] 17779.게리맨더링2(시뮬레이션).java  (0) 2020.09.03
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more