[Programmers] 무인도 여행 (JAVA)

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

---

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

 

Solution

import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;

public class 무인도여행 {
  public int[] solution(String[] maps) {
    char[][] graph = new char[maps.length][maps[0].length()];
    for (int y : IntStream.range(0, maps.length).toArray()) {
      for (int x : IntStream.range(0, maps[0].length()).toArray()) {
        char currentChar = maps[y].charAt(x);
        graph[y][x] = currentChar;
      }
    }
    LinkedList<Integer> answer = new LinkedList<Integer>();
    boolean[][] visitedPosition = new boolean[graph.length][graph[0].length];
    for (int y : IntStream.range(0, graph.length).toArray()) {
      for (int x : IntStream.range(0, graph[0].length).toArray()) {
        char currentDay = graph[y][x];
        if (currentDay != 'X' && !visitedPosition[y][x]) {
          Position position = new Position(x, y, currentDay);
          answer.add(bfs(graph, position, visitedPosition));
        }
      }
    }
    return answer.size() == 0 ? new int[] { -1 } : answer.stream().sorted((a, b) -> a - b).mapToInt((i) -> i).toArray();
  }

  private int bfs(char[][] graph, Position startPosition, boolean[][] visitedPosition) {
    int[] dX = { -1, 0, 1, 0 };
    int[] dY = { 0, 1, 0, -1 };
    Queue<Position> queue = new LinkedList<Position>();
    queue.add(startPosition);
    visitedPosition[startPosition.y][startPosition.x] = true;
    int maxHeight = graph.length;
    int maxWidth = graph[0].length;
    int total = 0;
    while (!queue.isEmpty()) {
      Position currentPosition = queue.poll();
      System.out.println(currentPosition.x + ", " + currentPosition.y + ", " + currentPosition.day + ", " + total);
      total += currentPosition.day;
      for (int i : IntStream.range(0, dX.length).toArray()) {
        int nextX = currentPosition.x + dX[i];
        int nextY = currentPosition.y + dY[i];
        if (nextX >= 0 && nextX < maxWidth && nextY >= 0 && nextY < maxHeight && graph[nextY][nextX] != 'X' && !visitedPosition[nextY][nextX]) {
          visitedPosition[nextY][nextX] = true;
          queue.add(new Position(nextX, nextY, graph[nextY][nextX]));
        }
      }
    }

    return total;
  }

  static class Position {
    public int x;
    public int y;
    public int day;

    Position (int x, int y, char day) {
      this.x = x;
      this.y = y;
      this.day = day == 'X' ? 0 : Character.getNumericValue(day);
    }
  }
}