[백준] 2146. 다리 만들기
2024. 4. 10. 14:55ㆍCS/Algorism
https://www.acmicpc.net/problem/2146
이 문제의 핵심은, 섬들의 가장자리에서 bfs로 바다를 탐색하면 된다. 그러다가 다른 섬을 만났을 때 이동한 카운트가 가장 작은 것이 정답이다.
이렇게 푸는데 있어서 흐름은 다음과 같다.
- 우선 각 섬들을 bfs해서 각 섬들에 번호를 매겨주어야 한다(2, 3, 4, ...). 이는 나중에 바다를 탐색하다가 섬에 닿았을 때 시작 섬과 도착 섬이 같은 섬인지 아닌지를 구분하기 위함이다.
- 또 한번 각 섬들을 bfs해서 각 섬들의 가장자리를 찾아낸다.
- 가장 자리를 찾았으면 바다로 bfs한다.
- 바다를 bfs하는 도중에 섬을 만났으면,
- 시작 섬과 같은 섬이면 pass하고,
- 시작 섬과 다른 섬이면 그 이동 거리를 정답 값으로 갱신할지말지 결정한다.
그리고 주의할 점은 다음과 같다.
- 1번을 수행한 후 visited 배열을 false로 초기화해야 한다. 그리고 2번을 수행해야 한다.
- 2-1번에서 바다를 탐색할 때는 각 탐색마다 seaVisited 배열이 매번 새로 생성되어야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n;
static int[][] map;
static boolean[][] visited;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
map = new int[n][n];
visited = new boolean[n][n];
// 0. map 초기화
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1. 각각의 섬을 탐색하면서 섬 번호를 매겨주기(2, 3, ...) (나중에 바다 탐색할 때 시작 섬과 도착 섬이 같은지 다른지 확인하기 위함)
int num = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
bfs(i, j, num++);
}
}
}
for (boolean[] arr : visited) {
Arrays.fill(arr, false);
}
// 2. 다시 각각의 섬을 탐색하다가 가장자리이면, 바다 탐색하기
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
bfs(i, j);
}
}
}
System.out.println(answer);
}
public static void bfs(int y, int x, int num) {
Queue<Node> que = new LinkedList<>();
visited[y][x] = true;
map[y][x] = num; // 번호 매겨주기
que.add(new Node(y, x));
while (!que.isEmpty()) {
Node now = que.poll();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + now.x;
int ny = dy[i] + now.y;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (visited[ny][nx]) continue;
// 다음 노드가 섬이면 계속 진행
if (map[ny][nx] == 1) {
visited[ny][nx] = true;
map[ny][nx] = num; // 번호 매겨주기
que.add(new Node(ny, nx));
}
}
}
}
public static void bfs(int y, int x) {
Queue<Node> que = new LinkedList<>();
visited[y][x] = true;
que.add(new Node(y, x));
while (!que.isEmpty()) {
Node now = que.poll();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + now.x;
int ny = dy[i] + now.y;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (visited[ny][nx]) continue;
// 다음 노드가 섬이면 계속 진행
if (map[ny][nx] == 1) {
visited[ny][nx] = true;
que.add(new Node(ny, nx));
}
// 다음 노드가 바다이면 바다 탐색 시작
if (map[ny][nx] == 0) {
seaBfs(ny, nx, map[now.y][now.x]);
}
}
}
}
public static void seaBfs(int y, int x, int startNum) {
Queue<Node> que = new LinkedList<>();
int[][] seaVisited = new int[n][n]; // 바다를 탐색할 때마다 매번 방문처리 배열은 새로 생성되어야 함
seaVisited[y][x] = 1;
que.add(new Node(y, x));
while (!que.isEmpty()) {
Node now = que.poll();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + now.x;
int ny = dy[i] + now.y;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (seaVisited[ny][nx] != 0) continue;
// 다음 노드가 섬이면
if (map[ny][nx] != 0) {
// 같은 섬이면 패스
if (map[ny][nx] == startNum) {
continue;
}
// 다른 섬이면 정답 갱신
else {
answer = Math.min(answer, seaVisited[now.y][now.x]);
return;
}
}
// 다음 노드가 바다이면 계속 진행
if (map[ny][nx] == 0) {
seaVisited[ny][nx] = seaVisited[now.y][now.x] + 1;
que.add(new Node(ny, nx));
}
}
}
}
public static class Node {
int y, x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
}
매번 알고리즘 문제 푸는 게 숙제처럼 느껴져서 대충 풀고 안되면 답 보고 그랬는데, 이번 문제는 진짜 혼자 힘으로 끝까지 고민해서 풀었다! 앞으로도 이렇게 하자..!
'CS > Algorism' 카테고리의 다른 글
[백준] 17182. 우주 탐사선 (0) | 2024.04.11 |
---|---|
[백준] 2531. 회전 초밥 (0) | 2024.04.10 |
소수인지 판단할 때 시간 복잡도 줄이기 (0) | 2024.03.21 |
[프로그래머스] 디스크 컨트롤러 (1) | 2024.03.07 |
[프로그래머스] 여행경로 (0) | 2024.03.06 |