Baekjoon 13459 구슬 탈출 - BFS

더 깔끔한 노션을 원한다면

Baekjoon 13459 구슬 탈출 - BFS

13459번: 구슬 탈출

설계

1. 상하좌우로 움직이는 것을 큐에 넣어준다.
2. O의 좌표가 될 때, 또는 횟수가 10이 넘었을 때 끝내준다.
3. 같은 줄에 빨간 공과 파란 공이 같이 있다면 상하좌우의 좌표를 잘 생각해줘야 한다.

1. 초기 큐

처음엔 빨간 구슬과 파란 구슬의 초기 좌표를 넣어준다

Queue<Point> redQueue = new LinkedList<>();
Queue<Point> blueQueue = new LinkedList<>();
for (int i = 0; i < N; i++) {
  for (int j = 0; j < M; j++) {
    if (board[i][j] == 'B') {
      blueQueue.add(new Point(i, j));
      board[i][j] = '.';
    } else if (board[i][j] == 'R') {
      redQueue.add(new Point(i, j));
      board[i][j] = '.';
    }
  }
}

2. 구멍 찾기

O의 좌표가 될 때, 또는 횟수가 10이 넘었을 때 끝내준다.

while (!redQueue.isEmpty() && count < 10) {
  count++;
  if (board[red.y][red.x] == 'O' && board[blue.y][blue.x] != 'O') {
    return 1;
  } else if (board[blue.y][blue.x] == 'O') {
    continue;
  }
  ...
}

대신 빨간 구슬과 파란 구슬이 모두 구멍이 들어갔을 때에는 예외처리해준다.

3. 상하좌우로 움직여주는 코드

한 칸씩 움직여주면서 확인해주는게 포인트! ( 내가 애먹은 부분 )

Point move(int y, int x, int d) {
  Point ball = null;
  int ny, nx;
  while (true) {
    ny = y + dy[d];
    nx = x + dx[d];
    if (isLimit(nx, ny)) {
      break;
    }
    if (board[ny][nx] == 'O') {
      ball = new Point(ny, nx);
      break;
    } else if (board[ny][nx] == '#') {
      ball = new Point(y, x);
      break;
    }
    y = ny;
    x = nx;
  }
  return ball;
}

#이나 O를 만났을 때, 그리고 범위 체크(isLimit)를 해줘야한다.

4. 구슬이 같은 줄에 있다면?

if (red.y == blue.y && red.x == blue.x) {  
  if (d == 0) {
    if (R.y < B.y) red.y -= 1;
    else blue.y -= 1;  
  } else if (d == 1) {  
    if (R.y > B.y) red.y += 1;
    else blue.y += 1;
  } else if (d == 2) {
    if (R.x < B.x) red.x -= 1;
    else blue.x -= 1;
  } else if (d == 3) {
    if (R.x > B.x) red.x += 1;
    else blue.x += 1;
  }
}

R은 이동하기 전 값, red는 이미 이동한 값이다.

전체 코드

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

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    System.out.println(solution.P13459());
  }
}

class Baekjoon {
  char[][] board;
  int dx[] = { 0, 0, 1, -1 };
  int dy[] = { 1, -1, 0, 0 };
  int N, M;

  public int P13459() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 세로
    M = Integer.parseInt(st.nextToken()); // 가로
    board = new char[N][M];
    int count = 0;
    Queue<Point> redQueue = new LinkedList<>();
    Queue<Point> blueQueue = new LinkedList<>();
    for (int i = 0; i < N; i++) {
      board[i] = br.readLine().toCharArray();
    }
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (board[i][j] == 'B') {
          blueQueue.add(new Point(i, j));
          board[i][j] = '.';
        } else if (board[i][j] == 'R') {
          redQueue.add(new Point(i, j));
          board[i][j] = '.';
        }
      }
    }
    while (!redQueue.isEmpty() && count < 10) {
      count++;
      int size = redQueue.size();
      for (int i = 0; i < size; i++) {
        Point R = redQueue.poll();
        Point B = blueQueue.poll();
        Point red = null;
        Point blue = null;
        for (int d = 0; d < 4; d++) {
          red = move(R.y, R.x, d);
          blue = move(B.y, B.x, d);
          if (board[red.y][red.x] == 'O' && board[blue.y][blue.x] != 'O') {
            return 1;
          } else if (board[blue.y][blue.x] == 'O') {
            continue;
          } else if (red.y == blue.y && red.x == blue.x) {
            if (d == 0) {
              if (R.y < B.y) {
                red.y -= 1;
              } else {
                blue.y -= 1;
              }
            } else if (d == 1) {
              if (R.y > B.y) {
                red.y += 1;
              } else {
                blue.y += 1;
              }
            } else if (d == 2) {
              if (R.x < B.x) {
                red.x -= 1;
              } else {
                blue.x -= 1;
              }
            } else if (d == 3) {
              if (R.x > B.x) {
                red.x += 1;
              } else {
                blue.x += 1;
              }
            }
          }
          redQueue.add(red);
          blueQueue.add(blue);
        }
      }
    }
    return 0;
  }

  Point move(int y, int x, int d) {
    Point ball = null;
    int ny, nx;
    while (true) {
      ny = y + dy[d];
      nx = x + dx[d];
      if (isLimit(nx, ny)) {
        break;
      }
      if (board[ny][nx] == 'O') {
        ball = new Point(ny, nx);
        break;
      } else if (board[ny][nx] == '#') {
        ball = new Point(y, x);
        break;
      }
      y = ny;
      x = nx;
    }

    return ball;
  }

  private boolean isLimit(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= M || ny >= N;
  }

  class Point {
    int y;
    int x;

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