[BOJ][2146] 다리 만들기
Updated:
1. 문제 링크
https://www.acmicpc.net/problem/2146
2. 사용 알고리즘
BFS
3. 풀이
단계별로 진행한다는 BFS의 성질을 이용
1) 입력값을 저장하기 위한 arr 배열, 그룹번호를 저장하기 위한 group 배열, 거리를 저장하기 위한 dist 배열 선언
2) (0, 0) 부터 차례대로 순회하며 BFS 탐색을 통해 인접한 육지를 같은 그룹번호로 저장
3) (0, 0) 부터 차례대로 순회하며 BFS 탐색을 위해 현재 육지인 곳의 인덱스를 큐에 저장하고, 거리를 0으로 저장
4) (0, 0) 부터 차례대로 순회하며 BFS 탐색을 통해 인접한 바다를 찾아 거리를 1씩 증가시키며 저장
5) (0, 0) 부터 차례대로 순회하며 상하좌우 좌표를 비교하여, 그룹번호가 다르고, 두 점의 거리의 합이 최소인 값을 찾아 출력
4. 소스 코드
4-1. C++
https://github.com/dev-aiden/problem-solving/blob/main/boj/2146.cpp
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
#include <iostream>
#include <queue>
using namespace std;
int arr[103][103];
int group[103][103];
int dist[103][103];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
cin >> arr[i][j];
}
}
int number = 1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(arr[i][j] == 1 && group[i][j] == 0) {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
group[i][j] = number;
while(!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int k = 0; k < 4; ++k) {
int ny = y + dy[k];
int nx = x + dx[k];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(arr[ny][nx] == 1 && group[ny][nx] == 0) {
q.push(make_pair(ny, nx));
group[ny][nx] = number;
}
}
}
}
++number;
}
}
}
queue<pair<int, int>> q;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
dist[i][j] = -1;
if(arr[i][j] == 1) {
dist[i][j] = 0;
q.push(make_pair(i, j));
}
}
}
while(!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(dist[ny][nx] == -1) {
dist[ny][nx] = dist[y][x] + 1;
group[ny][nx] = group[y][x];
q.push(make_pair(ny, nx));
}
}
}
}
int ans = -1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < 4; ++k) {
int ny = i + dy[k];
int nx = j + dx[k];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(group[i][j] != group[ny][nx]) {
if(ans == -1 || ans > dist[i][j] + dist[ny][nx]) {
ans = dist[i][j] + dist[ny][nx];
}
}
}
}
}
}
cout << ans << "\n";
return 0;
}
4-2. JAVA
https://github.com/dev-aiden/problem-solving/blob/main/boj/2146.java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair {
int y, x;
Pair(int y, int x) {
this.y = y;
this.x = x;
}
}
public class Main {
static int n;
static int arr[][] = new int[103][103];
static int group[][] = new int[103][103];
static int dist[][] = new int[103][103];
static int dx[] = {-1, 0, 1, 0};
static int dy[] = {0, -1, 0, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; ++j) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int number = 1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(arr[i][j] == 1 && group[i][j] == 0) {
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(i, j));
group[i][j] = number;
while(!q.isEmpty()) {
Pair p = q.remove();
for(int k = 0; k < 4; ++k) {
int ny = p.y + dy[k];
int nx = p.x + dx[k];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(arr[ny][nx] == 1 && group[ny][nx] == 0) {
q.add(new Pair(ny, nx));
group[ny][nx] = number;
}
}
}
}
++number;
}
}
}
Queue<Pair> q = new LinkedList<>();
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
dist[i][j] = -1;
if(arr[i][j] == 1) {
dist[i][j] = 0;
q.add(new Pair(i, j));
}
}
}
while(!q.isEmpty()) {
Pair p = q.remove();
for(int i = 0; i < 4; ++i) {
int ny = p.y + dy[i];
int nx = p.x + dx[i];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(dist[ny][nx] == -1) {
dist[ny][nx] = dist[p.y][p.x] + 1;
group[ny][nx] = group[p.y][p.x];
q.add(new Pair(ny, nx));
}
}
}
}
int ans = -1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < 4; ++k) {
int ny = i + dy[k];
int nx = j + dx[k];
if(ny >= 0 && ny < n && nx >= 0 && nx < n) {
if(group[i][j] != group[ny][nx]) {
if(ans == -1 || ans > dist[i][j] + dist[ny][nx]) {
ans = dist[i][j] + dist[ny][nx];
}
}
}
}
}
}
System.out.println(ans);
}
}
Leave a comment