백준 5852번: Island Travels (Java)

접근

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

5852번: Island Travels

문제 해석: R*C 크기의 지도에 15개 이하의 섬이 있습니다. 맞닿아 있는 경우에만 같은 섬이며, 바다는 수영할 수 있는 얕은 바다와 그럴 수 없는 깊은 바다로 나뉘어 있습니다. 베시가 헬리콥터로 이 지역에 도달하는데, 헬리콥터는 연료가 부족하여 베시를 한곳에만 내려줄 수 있습니다. 다행히도 섬들은 모두 수영해서 도달할 수 있도록 얕은 바다로 연결되어 있어, 베시는 모든 섬에 도착할 수 있습니다. 베시가 모든 섬을 방문할 수 있는 가장 적은 수영 횟수를 구하는 문제입니다.

그래프 방식을 이용하는 문제인 것은 한눈에 알 수 있어서 먼저 같은 섬들을 bfs를 통해 번호 매겼습니다. 이후에 섬들 사이의 거리(수영의 횟수)를 측정하여 cost 배열에 저장해주었습니다. cost[i][j] 는 i 섬에서 j 섬으로 이동할 때 필요한 수영 횟수를 뜻합니다.

다익스트라로 풀어야 하나 긴가민가 하다가 문제의 힌트를 확인했습니다. 문제의 힌트에서 비트마스크를 이용한다는 것을 보고, 비트마스크 및 DP를 이용하여 풀기로 합니다.

dp[1<<섬의갯수][섬의갯수] 로 초기화하여 dp[현재까지 탐색한 섬 목록][현재 섬] = 최소cost를 저장하도록 탐색합니다.

코드

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

public class Main {

  static int R, C;
  static char[][] map;
  static int[][] intmap;
  static int island_num;
  static int[] dr = { 0, 1, 0, -1 };
  static int[] dc = { 1, 0, -1, 0 };
  static int[][] cost;
  static int[][] dp;
  static int allvisit;

  static class Node implements Comparable<Node> {

    int val, r, c;

    public Node(int val, int r, int c) {
      this.val = val;
      this.r = r;
      this.c = c;
    }

    @Override
    public int compareTo(Node o) {
      return this.val - o.val;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    R = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());
    map = new char[R][C];
    intmap = new int[R][C];
    for (int i = 0; i < R; i++) {
      String input = br.readLine();
      for (int j = 0; j < C; j++) {
        map[i][j] = input.charAt(j);
      }
    }
    br.close();
    island_num = numberingAndGraph();
    dp = new int[1 << (island_num + 1)][island_num + 1];
    getAllVisit();
    int res = getSwinNumber(0, 0);
    System.out.println(res);
  }

  static boolean outMap(int r, int c) {
    return r < 0 || R <= r || c < 0 || C <= c;
  }

  // 섬들을 번호 매겨 intmap에 위치를 표시하고, 이 지도를 기반으로 섬에서 섬으로 이동하는데 몇번의 수영이 필요한지 탐색
  static int numberingAndGraph() {
    LinkedList<Node> queue = new LinkedList<>();
    int num = 1;
    // map을 탐색하면서 해당 위치가 섬이라면 bfs 탐색을 통해 같은 번호로 묶어줌
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (intmap[i][j] != 0 || map[i][j] != 'X') continue;
        queue.add(new Node(0, i, j));
        intmap[i][j] = num;
        while (!queue.isEmpty()) {
          Node now = queue.poll();
          for (int k = 0; k < 4; k++) {
            int nr = now.r + dr[k];
            int nc = now.c + dc[k];
            if (
              outMap(nr, nc) || intmap[nr][nc] != 0 || map[nr][nc] != 'X'
            ) continue;
            intmap[nr][nc] = num;
            queue.add(new Node(0, nr, nc));
          }
        }
        num++;
      }
    }
    // cost 배열을 만들고 cost[i][j] 는 i번 섬에서 j번 섬까지 이동하는데 몇번의 수영이 필요한지 저장
    cost = new int[num][num];
    // minimum 값을 저장하기 위해 max 값으로 초기화
    for (int i = 1; i < num; i++) {
      for (int j = 1; j < num; j++) {
        cost[i][j] = Integer.MAX_VALUE;
      }
    }
    PriorityQueue<Node> pq = new PriorityQueue<>();
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (map[i][j] != 'X') continue;
        int[][] visited = new int[R][C];
        pq.add(new Node(0, i, j));
        visited[i][j] = 1;
        int nown = intmap[i][j];
        while (!pq.isEmpty()) {
          Node now = pq.poll();
          for (int k = 0; k < 4; k++) {
            int nr = now.r + dr[k];
            int nc = now.c + dc[k];
            int nextD = now.val;
            if (
              outMap(nr, nc) ||
              visited[nr][nc] != 0 ||
              intmap[nr][nc] == nown ||
              map[nr][nc] == '.'
            ) continue;
            if (intmap[nr][nc] != 0) {
              cost[nown][intmap[nr][nc]] =
                Math.min(cost[nown][intmap[nr][nc]], nextD);
            } else {
              nextD++;
            }
            pq.add(new Node(nextD, nr, nc));
            visited[nr][nc] = 1;
          }
        }
      }
    }
    // 섬의 갯수를 리턴
    return num - 1;
  }

  static void getAllVisit() {
    for (int i = 1; i <= island_num; i++) {
      allvisit = (allvisit | 1 << i);
    }
  }

  // 비트마스크를 이용한 dp 탐색 함수
  static int getSwinNumber(int visit, int idx) {
    if (dp[visit][idx] != 0) return dp[visit][idx];
    if (visit == allvisit) return dp[visit][idx] = 0;
    int ret = Integer.MAX_VALUE;
    for (int next = 1; next <= island_num; next++) {
      if (idx == next || (visit & (1 << next)) != 0) continue;
      ret =
        Math.min(
          ret,
          getSwinNumber((visit | (1 << next)), next) + cost[idx][next]
        );
    }
    return dp[visit][idx] = ret;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!