https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static int[][] arr;
public static int[][] distance;
public static int[][] group;
public static int[] dirx = { 1, -1, 0, 0 };
public static int[] diry = { 0, 0, 1, -1 };
public static class Dot {
int x;
int y;
public Dot(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void grouping(int i, int j, int cnt) {
Queue<Dot> queue = new LinkedList<Dot>();
queue.add(new Dot(i, j));
while (!queue.isEmpty()) {
Dot d = queue.remove();
int x = d.x;
int y = d.y;
for (int k = 0; k < 4; k++) {
int nx = x + dirx[k];
int ny = y + diry[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (arr[nx][ny] == 1 && group[nx][ny] == 0) {// 중요!
group[nx][ny] = cnt;
queue.add(new Dot(nx, ny));
}
}
}
}
}
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());
arr = new int[n][n];
distance = new int[n][n];
group = new int[n][n];
// input
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// group
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 1 && group[i][j] == 0) {
group[i][j] = ++cnt;
grouping(i, j, cnt);
}
}
}
// distance
Queue<Dot> queue = new LinkedList<Dot>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
distance[i][j] = -1;
if (arr[i][j] == 1) {
queue.add(new Dot(i, j));
distance[i][j] = 0;
}
}
}
while (!queue.isEmpty()) {
Dot d = queue.remove();
int x = d.x;
int y = d.y;
for (int k = 0; k < 4; k++) {
int nx = x + dirx[k];
int ny = y + diry[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (distance[nx][ny] == -1) {
distance[nx][ny] = distance[x][y] + 1;
group[nx][ny] = group[x][y];
queue.add(new Dot(nx, ny)); // 큐 안에 넣어줘야함
}
}
}
}
int answer = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 4; k++) {
int x = i + dirx[k];
int y = j + diry[k];
if (x >= 0 && x < n && y >= 0 & y < n) {
if (group[x][y] != group[i][j]) {
answer = Math.min(answer, distance[i][j] + distance[x][y]);
}
}
}
}
}
System.out.println(answer);
}
}
|
cs |
처음에는 그룹으로 섬을 나눠야 겠다는 생각까진 했는데 거리를 어떻게 계산해주지? 라는 생각에서 막혔다.
뭔가 누적합을 배열에 써줘야 할 것 같은데 arr[X][Y]=arr[x][y]+1 ;을 해줘야 할 것 같은데 어떻게 해야할지 응용이 잘 안됐다.
30분정도 고민하다가 거리의 합을 효율적으로 구해줄 수 있는 아이디어를 발견했다.
백준 2146 / 다리 만들기 / BFS / JAVA / 골드 3
오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는
devowen.com
위 링크인데, 처음에는 그룹으로 묶는 것도 Dot클래스에 넣어주려다가
글을 보니 group배열도 새로 만들어서 푸는게 더 나을 것 같아서 배열을 만들어 풀었다.
물론 효율성만 따질 땐 다른 코드가 좋다고 말하는 사람도 있겠지만 가장 직관적이고 이해가 잘돼서 나중엔 아이디어만 머리속에 넣고 내가 스스로 구현할 수 있었다!!
배열을 3개 만드는데
입력을 받아줄 배열
그룹으로 묶어줄 배열
--> arr[i][j]==1이면 group[i][j]==1 큐가 비어있으면 cnt값을 하나더 올려주고, 큐가 비어있기 전까지 group[i][j]==2 이런식으로 계속 더해준다
인접한 노드인 애들이 같은 그룹이고, 걔네들을 계속 큐에 넣어주는 거기 때문에 bfs 사용하면된다.
거리를 계산해주는 배열
arr[i][j]=1 이면 distance[i][j]=0
arr[i][j]=0 이면 distance[i][j]=-1로 이중 for문을 돌려서 세팅해준다.
arr[i][j]==1 인 경우 그 i,j 값을 큐에 넣어준다.
큐가 비어있기 전까지 distance[nx][ny]=-1 이면 (바다인 경우, 다리를 놓아주기 위해)
distance[nx][ny]=distance[x][y]+1; //다리를 놓아준 곳 까지 거리(distance[x][ny]까지 가기 위한 다리의 길이 총합)를 누적합으로 표시
group[nx][ny]=group[x][y]; // 다리를 놓아준 섬을 기준으로 자기네 그룹으로 만드는거
만약 group[x][y]!=group[i][j] 라면 서로 다른 그룹 출신의 다리 이므로 group[x][y]까지의 누적합(즉, group[x][y]의 값)과 group[i][j]까지의 누적합을 더해주면 다리의 길이가 나온다!
더 자세한건 링크를 타고 가서 보면된다. 정말 설명을 너무 잘해놓으셨다!! 나도 저렇게 직관적인 아이디어로 알고리즘을 짜고 싶다..!
문제를 풀면서 잘 못 했던 점
하지만 그럼에도 불구하고 자꾸 메모리 초과,시간 초과가 났다. 심지어 이클립스가 느려지기까지 했다.. heap space 부족으로..ㅋㅋ
이유는 큐에 원소를 넣어주지 않아서/ 조건을 걸어두지 않아서 였다!
1. 조건을 걸어두지 않아서
grouping() 메서드에서
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (arr[nx][ny] == 1 && group[nx][ny] == 0) {// 중요!
group[nx][ny] = cnt;
queue.add(new Dot(nx, ny));
}
}
--> 노란색으로 강조처리된 코드를 안썼다.. 당연히 arr[nx][ny]==1(섬인 부분) 이면서 그룹화가 안된 경우에 cnt값(그룹 번호)을 넣어주는 건데 저걸 안하면 뒤에 코드까지 같이 꼬인다..ㅜ
2.큐에 원소를 넣어주지 않아서
for (int k = 0; k < 4; k++) {
int nx = x + dirx[k];
int ny = y + diry[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (distance[nx][ny] == -1) {
distance[nx][ny] = distance[x][y] + 1;
group[nx][ny] = group[x][y];
queue.add(new Dot(nx, ny)); // 큐 안에 넣어줘야함
}
}
}
--> 마지막에 거리 구할 때, 다리를 계속 놓아주려면 인접 노드를 큐에 넣어줘야 하는데 큐 안에 넣어주지 않았다.
너무 당연한 소리지만 큐를 만들었으면 큐에 원소를 넣어야 한다..ㅋㅋ
큐를 통해서 bfs를 푸는거에 더욱 익숙해져서 문제가 나에게 준 의의는 크다! 또 다른 bfs 문제들을 스스로 풀어내고 싶다!
'알고리즘 > 그래프' 카테고리의 다른 글
| [java 백준] 실버 1/ 1991번 트리 순회 (0) | 2021.11.09 |
|---|---|
| [트리개념] Binary Tree와 순회방법 (0) | 2021.11.04 |
| [java 백준]실버 1/2178번 미로찾기 (0) | 2021.10.09 |
| [java 백준] 실버 1/7576번 토마토 (0) | 2021.10.03 |
| [java 백준]실버 1/ 7569번 토마토 (0) | 2021.10.03 |
댓글