2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
- 생각
dfs방식으로 풀면 될 것 같다라고 생각한다.
dfs방식
1. 모든 섬의 칸을 queue에 넣는다.
2. bfs를 돌린다. (0을 만나면 시작)
3. 섬을 만나면 return하면서 지나온 0의 칸수와 지금까지 가장 짧았던 0의 칸수로 비교
==> 문제가 되는 것은 bfs를 돌면서 같은 섬으로 갈 수 있다는 것
참고)
백준 2146 / 다리 만들기 / BFS / JAVA / 골드 3
오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는
devowen.com
이제 문제를 보도록 하자. N X N의 배열이 주어지고 섬이 있는 곳은 1, 없는 곳은 0으로 input 값이 들어온다. 나는 이 값을 받는 inputArr 행렬을 하나 만들고, 각 섬들을 그룹화한 groupArr, 섬으로부터의 거리를 나타낸 distArr 이렇게 세 개의 배열을 만들어서 문제를 풀었다. groupArr는 섬을 한 그룹씩 순서대로 인덱싱을 해서 1,2,3, .. 이런식으로 같은 섬은 같은 숫자를 입력해 주었다. 그리고 distArr는 섬인 경우는 초기값을 0으로 나머지는(섬이 아닌 곳) -1로 해서 구분을 해 주었다. (그림에서 빈 칸은 모두 초기값 0이며 생략했다)
이렇게 만들고 나서 distArr에서 BFS를 통해 모든 점에 대해 섬에서부터 거리가 얼마나 되는지를 계산한다. 섬 위에 있다면 당연히 그 값은 0이다. 그리고 그 섬에서 인접한 값들은 1이고 그 값에서 인접한 값은 2일 것이다. 그런식으로 -1로 초기에 설정된 점들은 섬들로부터 최단거리를 계산해서 그 값을 넣어 준다.
이렇게 거리를 계산하다보면 인접한 점의 distArr 배열값이 이미 자연수로 정해진 경우가 있다. 그 경우는 값을 갱신해 주지 않는다. 즉, distArr에서 모든 점을 탐색하고 나면 각각의 점은 섬으로부터의 최단 거리가 되는 것이다. 그렇게 계산을 마치면, distArr에서 임의의 한 점과 그 인접한 점의 합이 최소가 되는 점을 찾는다. 그 값이 최단거리가 되는 것이다.
물론 BFS로 계산을 하는 것이니, 거리가 1인 점들을 다 찾고 그 다음 거리가 2인 점을 찾을 것이다. 즉 값을 입력하는 순서가 거리 오름차순이라는 의미이다. 따라서 인접한 두 점이 발견되면 바로 그 순간 두 섬 사이의 거리를 계산해서 리턴해 주어도 된다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Algorithm {
static int N, answer, array[][], distanceArray[][], groupArray[][];
static int[] x = { 0, 0, 1, -1 };
static int[] y = { 1, -1, 0, 0 };
public static void main(String[] args) throws Exception {
SetData();
bfs();
System.out.println(answer);
}
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
array = new int[N][N];
distanceArray = new int[N][N];
groupArray = new int[N][N];
answer = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
array[j][i] = in.nextInt();
}
}
}
private static void bfs() {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (array[i][j] != 1 || groupArray[i][j] != 0)
continue; // array가 1이고 g를 초기화 안했다면
Queue<int[]> queue = new LinkedList<>();
groupArray[i][j] = ++count; // g를 초기화
queue.add(new int[] { i, j });
while (!queue.isEmpty()) {
int[] location = queue.remove();
for (int k = 0; k < 4; k++) {
int r = location[0] + x[k];
int c = location[1] + y[k];
if (r < 0 || r >= N || c < 0 || c >= N)
continue;
if (array[r][c] == 1 && groupArray[r][c] == 0) {
queue.add(new int[] { r, c });
groupArray[r][c] = count;
}
}
}
}
}
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
distanceArray[i][j] = -1;
if (array[i][j] == 1) {
queue.add(new int[] { i, j });
distanceArray[i][j] = 0;
}
}
}
while (!queue.isEmpty()) {
int[] location = queue.remove();
for (int k = 0; k < 4; k++) {
int r = location[0] + x[k];
int c = location[1] + y[k];
if (r < 0 || r >= N || c < 0 || c >= N)
continue;
if (distanceArray[r][c] == -1) {
distanceArray[r][c] = distanceArray[location[0]][location[1]] + 1;
groupArray[r][c] = groupArray[location[0]][location[1]];
queue.add(new int[] { r, c });
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 4; k++) {
int r = i + x[k];
int c = j + y[k];
if (r < 0 || r >= N || c < 0 || c >= N)
continue;
if (groupArray[i][j] != groupArray[r][c])
answer = Math.min(answer, distanceArray[i][j] + distanceArray[r][c]);
}
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 1987번 : 알파벳 (0) | 2021.02.10 |
|---|---|
| [BOJ/JAVA] 백준 16194번 : 카드 구매하기 2 (0) | 2021.02.09 |
| [BOJ/JAVA] 백준 14500번 : 테트로미노 (0) | 2021.02.08 |
| [BOJ/JAVA] 백준 15684번 : 사다리 조각 (0) | 2021.02.08 |
| [BOJ/JAVA] 백준 1083번 : 소트 (0) | 2021.02.05 |
