[백준/1261] 알고스팟 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1261
• 분류 : BFS, 다익스트라
• 풀이 시간 : 40분

문제 해설

1. 알고스팟 운영진이 N*M 크기의 미로에 갇힘
2. 탈출하기 위해 동, 서 , 남, 북 방향으로 움직일 수 있음
3. 0 빈 방, 1 벽
4. 벽을 만나면 부수고 이동할 수 있음
5. (1, 1)부터 시작해서 (N, M)까지 이동하려할 때, 벽을 최소 몇 개 부수어야할까?

Solution

풀이 접근 방법

1. 동, 서, 남, 북 방향으로 이동 & 목적지까지 가는 최소 방법 = BFS
2. 목적지까지 가는 최소 방법
   1. 특정 좌표로 가는 방법 = 벽을 부수거나, 부수지 않고 가는 방법 2가지
   2. 만약 누군가 특정 좌표로 갈 때, 벽을 i개 부수고 가는 방법과 한번도 부수지 않고 갈 수 있다면
      1. 벽을 더 적게 부수는 방법 선택
   3. int[][] visited = x, y 좌표로 가기 위해 벽을 몇개 부숴야 하는지 저장
      1. 새로 방문한 방법이 이미 저장된 값보다 더 적게 벽을 부수고 도착했다면
      2. 새롭게 도착한 값(breakCnt)로 다시 탐색 시작하도록 큐에 넣음

정답 코드

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

public class Main {
  static class Manager {
    int x, y, breakCnt;

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

    public void breakWall() {
      this.breakCnt += 1;
    }
  }

  static int N, M;

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

    M = Integer.valueOf(st.nextToken());
    N = Integer.valueOf(st.nextToken());
    int[][] map = new int[N][M];

    for (int i = 0; i < N; i++) {
      String[] info = br.readLine().split("");

      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.valueOf(info[j]);
      }
    }

    bw.write(goToDestination(map) + "\n");
    bw.flush();
    bw.close();
  }

  static int goToDestination(int[][] map) {
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };
    int[][] visited = new int[N][M];
    Queue<Manager> queue = new LinkedList<Manager>();

    // x, y 까지 왔을 때 벽을 부순 최소 개수를 표시하기 위해 전제 배열의 값 최대로 초기화
    for (int i = 0; i < N; i++)
      Arrays.fill(visited[i], 987654321);

    visited[0][0] = 0;
    queue.add(new Manager(0, 0, 0));

    while (!queue.isEmpty()) {
      Manager current = queue.poll();

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

        // 방의 범의 범위를 벗어나면 안됨
        if (!isIn(nx, ny))
          continue;

        // 목적지에 도착했을 때
        if (nx == N - 1 && ny == M - 1) {
          // 목적지까지 왔을 때 부순벽의 개수를 저장되어있는 값이랑 비교해서 더 작은 값 저장
          visited[nx][ny] = Math.min(breakCnt, visited[nx][ny]);
          continue;
        }

        // 다음에 가야할 칸이 벽이면 부숨
        if (map[nx][ny] == 1)
          breakCnt += 1;

        // 누군가가 이미 그 칸으로 이동했을 때 저장한 부순 벽의 개수 <= 다음 칸으로 이동하기 위해 벽을 부순 개수
        if (visited[nx][ny] <= breakCnt)
          continue;

        // 이미 저장된 값보다 더 적게 부숴야 그 칸으로 이동할 수 있음
        queue.add(new Manager(nx, ny, breakCnt));
        visited[nx][ny] = breakCnt;
      }
    }

    return visited[N - 1][M - 1];
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < M)
      return true;
    return false;
  }

}