문제

보물섬

---

문제 이해

• L(Land)와 W(Water)를 입력 받는다
• 후크 선장은 L만 이동할 수 있다.
• 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간 -> BFS
• DFS로는 성능 저하

---

코드

메모리 부족 코드

import java.io.*;
import java.util.*;

public class TreasureSearch {
  static int R; // row
  static int C; // col
  static int answer;

  static String[][] map; // treasure map
  static int[][] canMove = new int[][] { // 이동 가능한 부분
      { -1, 0 },
      { 1, 0 },
      { 0, -1 },
      { 0, 1 }
  };

  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 String[R][C];

    for (int i = 0; i < R; i++) {
      st = new StringTokenizer(br.readLine());
      map[i] = st.nextToken().split("");
    }

    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (map[i][j].equals("L")) {
          int result = bfs(i, j);

          if (answer < result)
            answer = result;
        }
      }
    }

    System.out.println(answer);
  }

  public static int bfs(int x, int y) {
    boolean[][] isVisited = new boolean[R][C];
    Queue<Integer[]> queue = new LinkedList<>();
    int[][] longDistance = new int[R][C];
    int maxNum = 0;
    queue.add(new Integer[] { x, y });

    while (!queue.isEmpty()) {

      // queue 하나 빼기
      Integer[] current = queue.poll();

      // 방문 여부 변경
      isVisited[current[0]][current[1]] = true;
      for (int i = 0; i < canMove.length; i++) {
        // 다음 위치
        Integer[] next = new Integer[] { current[0] + canMove[i][0], current[1] + canMove[i][1] };

        // index 벗어날때 continue
        if (next[0] < 0 || next[1] < 0 || next[0] >= R || next[1] >= C) {
          continue;
        }

        // "L"일때 queue add
        if (map[next[0]][next[1]].equals("L") && !isVisited[next[0]][next[1]]) {
          queue.add(new Integer[] { next[0], next[1] });
          longDistance[next[0]][next[1]] = Math.max(longDistance[current[0]][current[1]] + 1,
              longDistance[next[0]][next[1]]);
          if (maxNum < longDistance[next[0]][next[1]])
            maxNum = longDistance[next[0]][next[1]];
        }

      }
    }
    longDistance = null;
    // return Arrays.stream(longDistance)
    // .flatMapToInt(arr -> Arrays.stream(arr))
    // .max()
    // .getAsInt();
    return maxNum;
  }
}

메모리 문제 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class TreasureSearch {
  public static class Location {
    int row;
    int col;
    int distance;

    public Location(int row, int col, int distance) {
      this.row = row;
      this.col = col;
      this.distance = distance;
    }
  }

  static int R; // row
  static int C; // col
  static int answer;
  static boolean[][] isVisited;
  static int maxNum;
  static char[][] map; // treasure map
  static int[] canMoveR = { -1, 1, 0, 0 };
  static int[] canMoveC = { 0, 0, -1, 1 };

  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];

    for (int i = 0; i < R; i++) {
      map[i] = br.readLine().toCharArray();
    }

    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (map[i][j] == 'L') {
          bfs(i, j);
        }
      }
    }
    /* 메모리 확인 코드
    Runtime.getRuntime().gc();
    long usedMemory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
    System.out.print(usedMemory + " bytes");
    */
    System.out.println(answer);
    br.close();
  }

  public static void bfs(int x, int y) {
    isVisited = new boolean[R][C]; // visited check
    Queue<Location> queue = new LinkedList<Location>();
    maxNum = 0;
    queue.add(new Location(x, y, 0));
    isVisited[x][y] = true;
    while (!queue.isEmpty()) {
      // queue 하나 빼기
      Location current = queue.poll();

      for (int i = 0; i < 4; i++) {
        // 다음 위치
        int nextR = current.row + canMoveR[i];
        int nextC = current.col + canMoveC[i];

        // index 벗어나지 않을때
        if (nextR >= 0 && nextC >= 0 && nextR < R && nextC < C) {

          // "L"일때 queue add
          if (map[nextR][nextC] == 'L' && !isVisited[nextR][nextC]) {
            // 방문 여부 변경
            isVisited[nextR][nextC] = true;

            queue.add(new Location(nextR, nextC, current.distance + 1));
            answer = Math.max(answer, current.distance + 1);
          }
        }
      }
    }
  }
}

• 개선한 사항

1. map(2d String array) -> map(2d char array)
2. canMove(2d int array) -> canMoveR, canMoveC로 분할(4번만 돌게끔)
3. Integer 배열보단 int형 두개에 값을 저장해 가독성 좋게 변경
4. 최대값 두번 구하지 말고 한번에 bfs 함수 내에서 구하기
5. Location class 선언해서 따로 길이 담고 있는 2d array 사용하지 않기
6. 방문했다는 확인 코드 위치 변경

---

코드 설명

1. 보물섬 지도 matrix를 입력받고 matrix를 탐색한다.
2. 현재 위치가 L이라면 bfs 함수를 호출해 BFS 실행한다.
3. 방문했는지 확인하는 배열, Queue 초기화
4. 현재 위치를 Queue에 넣고 현재 위치를 방문했다고 표시
5. Queue가 빌때까지 반복
   5-1. Queue에서 하나 poll 한다
   5-2. 해당 위치에서 상, 하, 좌, 우를 탐색하며 L이고 보물섬 지도 내에 위치한다면 Queue에 넣고 방문했다고 표시한다.
   5-3. 이때 Queue에 넣은 위치는 다음 위치이기 때문에 현재 위치에서 1을 더한 거리를 넣고 최댓값을 찾는다

메모리 추가로 너무 고생했다... 메모리도 고려하자!

---