[JAVA] 백준 2146 다리 만들기

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

2146번: 다리 만들기

 

1. 서론

 

골3 치고는 어렵지 않은, 그러나 오히려 커다란 교훈을 준 문제이다. 근데 이 문제가 나에게 쉬웠던 이유는 예전에 이와 비슷한 문제를 푼 경험이 있기 때문이다. swea 문제였던 것 같은데 블로그에는 없는데 어쨌든 풀어 본 경험이 날 도와줬다.

 

2. 문제 풀이

 

여러 대륙이 주어지고 그 대륙들은 모두 처음에는 떨어져 있다고 가정한다. 그랬을 때 대륙간을 연결하는 최솟값을 구하는 게 이 문제이다.

그래서 약간의 삽질 후에 방법을 떠올려서 그대로 구현했다.

 

1) 각 대륙을 식별하기 위해 대륙별로 idx를 정해서 그 대륙을 전부 그 idx로 바꿔주기(bfs)

2) 각 대륙의 마지막 부분에서 다른 대륙으로 bfs(연결 최솟값 구하기 위해), 도착하면 Math.min

 

논리는 이렇게 간단한데 하루종일 문제를 풀지 못했다. 이론상으로 틀린 것도 없는데 왜 안될까 했더니 계속 메모리초과가 났다.

그래서 내가 뭔가를 잘못푼건가 싶어서 어쩔 수 없이 구글링을 해서 답들을 찾아봤는데 답들이랑 나랑 논리적으로 다른 게 하나도 없었다.

그래서 더 열받았다... 결국에 메모리 초과의 원인은?

 

while (!q.isEmpty()) {
      Point p = q.poll();
      map[p.x][p.y] = idx;
      visit[p.x][p.y] = true;
      for (int k = 0; k < 4; k++) {
        int nx = p.x + dx[k], ny = p.y + dy[k];
        if (range(nx, ny) && !visit[nx][ny] && map[nx][ny] == 1)
            q.add(new Point(nx, ny));
      }
    }

 

바로 이 문제였다. 논리적으로는 당연히 문제가 없지만, n이 최대 100이기 때문에 경우의 수가 많아지면서 생기는 문제였다.

코드를 보면 큐에서 빼고나서 방문처리를 해주는데 나는 이 코드를 작성할 때만 해도 조삼모사로 생각했다. 결과적으로는 다 체크를 해주니까, 위에 따로 visit[0][0] = true 이걸 써주기가 싫어서 그냥 큐에서 뺐을때 방문처리를 하게 해 줬다. 근데 이게 메모리 초과의 원인이었다.

생각해 보면 당연하긴 하다. 하나의 값이 들어가면 최소 4번을 탐색하고 조건에 맞는 값을 또 넣어줘야 하는데 그게 약간 쓸데없이 다 탐색해서 시간이 오래 걸리는 거였다. 저것만 for문 안으로 넣어줬더니 바로 맞아버려서 너무 놀랐다. (이게 문제일 거라고 생각 못했기 때문에)

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
  static int[] dx = {0, 1, -1, 0}, dy = {1, 0, 0, -1};
  static int n, ans = Integer.MAX_VALUE;
  static int[][] map;
  static boolean[][] visit;
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());
    map = new int[n][n];

    for (int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++)
        map[i][j] = Integer.parseInt(st.nextToken());
    }

    int idx = 2;//그룹별 번호 먹임
    visit = new boolean[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (map[i][j] == 1 && !visit[i][j]) {
          bfs(new Point(i, j), idx);
          idx++;//번호 카운트
        }
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (map[i][j] > 1) {
          visit = new boolean[n][n];
          bridge(new Len(i, j, 0), map[i][j]);
        }
      }
    }

    System.out.print(ans);
  }

  public static void bfs(Point s, int idx) { //번호 식별
    Queue<Point> q = new ArrayDeque<>();
    q.add(s);
    map[s.x][s.y] = idx;
    visit[s.x][s.y] = true;

    while (!q.isEmpty()) {
      Point p = q.poll();

      for (int k = 0; k < 4; k++) {
        int nx = p.x + dx[k], ny = p.y + dy[k];
        if (range(nx, ny) && !visit[nx][ny] && map[nx][ny] == 1) {
          map[nx][ny] = idx;
          visit[nx][ny] = true; //이렇게 안쪽으로 줄여주면 시간이 엄청 줄어듬
          q.add(new Point(nx, ny));
        }
      }
    }
  }

  public static void bridge(Len l, int idx) { //다리 최솟값찾기 이동
    Queue<Len> q = new ArrayDeque<>();
    q.add(l);
    visit[l.x][l.y] = true;

    while (!q.isEmpty()) {
      Len p = q.poll();
      if (ans <= p.cnt) continue;
      for (int k = 0; k < 4; k++) {
        int nx = p.x + dx[k], ny = p.y + dy[k];
        if (range(nx, ny) && !visit[nx][ny] && map[nx][ny] != idx) { //방문한 적 없는 곳일때
          if (map[nx][ny] == 0) {//바다라면 마저탐색
            q.add(new Len(nx, ny, p.cnt + 1)); //큐에 넣음
            visit[nx][ny] = true; //방문체크
          }
          else //바다 아니면 다른 대륙이므로 최솟값 구하기
            ans = Math.min(ans, p.cnt);
        }
      }
    }
  }

  public static boolean range(int nx, int ny) {
    if (nx >= 0 && nx < n && ny >= 0 && ny < n) return true;
    return false;
  }

  static class Len{
    int x, y, cnt;
    public Len(int x, int y, int cnt) { //x,y 좌표와 이동거리를 cnt로 정의했다.
      this.x = x;
      this.y = y;
      this.cnt = cnt;
    }
  }
}

 

주석 참조~@@