BOJ) 다리 만들기

다리 만들기

2146번: 다리 만들기

여러 섬으로 이루어진 나라에서 가장 가까운 두 섬을 잇는 최단 거리 비용을 구하는 문제다.

최단 거리라고해서 해당 알고리즘들을 사용할 수 있을까 고민했는데, 떠오르지 않았다.

그래서 평소에 즐겨하던 grouping을 하면서, 모든 섬마다 전체 좌표를 List에 저장했다.

또한, 각 섬마다 위치를 식별할 수 있어야해서 위의 섬의 좌표를 저장하는 List를 List에 저장해주었다.

List<List<Island Position>> 으로 섬의 모든 좌표를 저장해주었다.

 

좌표를 모두 저장한 이후에는 각 섬들의 최소 연결비용을 구하며 답을 구해주었다.N이 100이하의 자연수로 주어지기 때문에, 모든 위치를 탐색했다.

시간 효율이 뛰어나지 않아서 더 좋은 방법이 있을까 고민해봤지만, 아직은 잘 모르겠다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class MakeBridge_2146 {
  static final int DIRECTIONS = 4;
  static final int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};

  static int n;
  static boolean[][] map;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    map = new boolean[n][n];
    final String ISLAND = "1";

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

    br.close();
    solution();
  }

  private static void solution() {
    boolean[][] visit = new boolean[n][n];
    List<List<Pos>> islandList = new ArrayList<>();
    setIslandList(visit,islandList);

    int answer = Integer.MAX_VALUE;
    int size = islandList.size();
    for(int i=0; i<size; i++) {
      for(int j=0; j<size; j++) {
        if(i!=j) {
          answer = Math.min(answer, getDist(islandList.get(i), islandList.get(j)));
        }
      }
    }

    System.out.println(answer);
  }

  private static int getDist(List<Pos> originList, List<Pos> targetList) {
    int result = Integer.MAX_VALUE;

    for(Pos origin : originList) {
      for(Pos target : targetList) {
        result = Math.min(result, Math.abs(origin.x - target.x) + Math.abs(origin.y - target.y) -1);
      }
    }
    return result;
  }

  private static void setIslandList(boolean[][] visit, List<List<Pos>> islandList) {
    for(int y=0; y<n; y++) {
      for(int x=0; x<n; x++) {
        if(!visit[y][x] && map[y][x]) {
          Queue<Pos> queue = new LinkedList<>();
          queue.offer(new Pos(x,y));
          islandList.add(getIslandPosList(queue, visit));
        }
      }
    }
  }

  private static List<Pos> getIslandPosList(Queue<Pos> queue, boolean[][] visit) {
    List<Pos> islandPosList = new ArrayList<>();
    Pos start = queue.peek();
    visit[start.y][start.x] = true;

    while(!queue.isEmpty()) {
      Pos now = queue.poll();
      islandPosList.add(now);
      for(int i=0; i<DIRECTIONS; i++) {
        int nx = now.x + dx[i], ny = now.y + dy[i];
        if(isInRange(nx,ny) && !visit[ny][nx] && map[ny][nx]) {
          queue.offer(new Pos(nx, ny));
          visit[ny][nx] = true;
        }
      }
    }
    return islandPosList;
  }

  private static boolean isInRange(int x, int y) {
    return x>=0 && x<n && y>=0 && y<n;
  }

  private static class Pos {
    int x, y;

    public Pos(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}