BOJ-2589 보물섬

1. 문제

문제 링크 : https://www.acmicpc.net/problem/2589

알고리즘 분류 : 브루트포스 알고리즘, 너비 우선 탐색

2. 고민

보물 지도의 가로, 세로의 크기는 각각 50이하이기 때문에 각 지점에 대해

Brute Force 알고리즘과 BFS 조합으로 충분히 풀 수 있다고 생각했습니다.

3. 1차 시도 (성공)

  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 Main {
    private static int row, col;                            // 보물지도 세로, 가로
    private static int result;                              // 보물의 최단 거리
    private static char[][] map;                            // 보물 지도
    private static int[] dy = {-1, 1, 0, 0};                // 상.하.좌.우 y 값
    private static int[] dx = {0, 0, -1, 1};                // 상.하.좌.우 x 값
    private static boolean[][] visit;                       // 방문 체크 배열
    private static Queue<Point> que = new LinkedList<>();   // BFS용 Queue

    private static class Point {
      int y, x, cnt;

      Point(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
      }
    }

    /* BFS */
    private static void bfs() {
      while(!que.isEmpty()) {
        Point front = que.poll();
        result = Math.max(result, front.cnt);

        for(int idx=0; idx<4; idx++) {
          int y = front.y + dy[idx];
          int x = front.x + dx[idx];

          if(y < 0 || y >= row || x < 0 || x >= col)  continue;
          if(map[y][x] == 'W' || visit[y][x])    continue;

          visit[y][x] = true;
          que.add(new Point(y, x, front.cnt + 1));
        }
      }
    }

    /* visit 배열 초기화 */
    private static void clearVisit() {
      for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++)
          visit[i][j] = false;
      }
    }

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      row = Integer.parseInt(st.nextToken());
      col = Integer.parseInt(st.nextToken());

      map = new char[row][col];
      visit = new boolean[row][col];

      for(int i=0; i<row; i++)
        map[i] = br.readLine().toCharArray();
      
      // Brute Force 알고리즘
      for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++) {
          if(map[i][j] == 'W')    continue;

          clearVisit();
          visit[i][j] = true;
          que.add(new Point(i, j, 0));
          bfs();
        }
      }

      System.out.println(result);
    }
  }

4. 2차 시도 (성공)

1차 시도는 무난히 통과했지만, 시간과 메모리가 492 ms와 291788 KB로 성능이 좋지 않았습니다.

그래서 다른 분들의 코드를 참조해보았습니다.

다른 분들은 Brute Force 알고리즘 대신 시작점을 찾아 그 시작점에서만 BFS를 사용했습니다.

예를 들면 위의 그림에서 빨간 부분은 어떻게 하더라도 최단 거리가 될 수 없는 점을 이용하는 것입니다.

이를 이용한 코드는 다음과 같습니다.

  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 Main {
    private static int row, col;                // 보물지도 세로, 가로
    private static int result;                  // 보물의 최단 거리
    private static char[][] map;                // 보물 지도
    private static int[] dy = {-1, 1, 0, 0};    // 상.하.좌.우 y 값
    private static int[] dx = {0, 0, -1, 1};    // 상.하.좌.우 x 값

    /* 큐에 넣을 Point 객체 */
    private static class Point {
      int y, x, cnt;

      Point(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
      }
    }

    /* BFS */
    private static void bfs(int y, int x) {
      Queue<Point> que = new LinkedList<>();
      boolean[][] visit = new boolean[row][col];

      que.add(new Point(y, x, 0));
      while(!que.isEmpty()) {
        Point front = que.poll();
        visit[front.y][front.x] = true;
        result = Math.max(result, front.cnt);

        for(int idx=0; idx<4; idx++) {
          int ny = front.y + dy[idx];
          int nx = front.x + dx[idx];

          if(!isValidPoint(ny, nx))  continue;
          if(map[ny][nx] == 'W' || visit[ny][nx])    continue;

          visit[ny][nx] = true;
          que.add(new Point(ny, nx, front.cnt + 1));
        }
      }
    }

    /* 시작점 조회 */
    // 현재 위치가 중간 위치라면 그 지점은 시작점이 아니다.
    // o + o    => + 위치는 어떻게 해도 최단 거리가 아님
    private static boolean isStartPoint(int y, int x) {
      int hcount = 0, wcount = 0, count = 0;

      for(int idx=0; idx<4; idx++) {
        int ny = y + dy[idx];
        int nx = x + dx[idx];

        if(!isValidPoint(ny, nx))   continue;
        if(map[ny][nx] == 'L'){
          count++;
          if(idx == 0 || idx == 1) hcount++;
          else wcount++;
        }
      }

      return count == 1 || (count == 2 && wcount == 1 && hcount == 1);
    }

    /* 보물지도 유효 범위 조회 */
    private static boolean isValidPoint(int y, int x) {
      return y >= 0 && y < row && x >= 0 && x < col;
    }

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      row = Integer.parseInt(st.nextToken());
      col = Integer.parseInt(st.nextToken());

      map = new char[row][col];
      for(int i=0; i<row; i++)
        map[i] = br.readLine().toCharArray();

      for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++) {
          if(map[i][j] == 'L' && isStartPoint(i, j))
            bfs(i, j);
        }
      }

      System.out.println(result);
    }
  }

            
              📕 개인 기록용 블로그입니다.
              😊 오타나 잘못된 정보가 있을 경우 댓글이나 메일로 말씀해주시면 바로 수정하겠습니다! 😊