[java,백준13460]구슬 탈출 2 - BFS와 DFS

BFS와 DFS(중복순열) 둘 다 구할 수 있고, 벽 끝까지 이동하는 빨간 구슬을 구멍으로 빼내는 최소 이동 횟수를 구하는 문제입니다.

구슬 탈출 2(백준13460)


1가지 예시를 들자면, “#…RB#” 일 때 왼쪽 기울이기를 1번 한다면? “#RB…#” 이 된다. 왜??

  • ”.” 은 빈 공간이라 지나가고 “#”은 벽이라 멈추고 마지막은 구슬끼리 부딪혀서 멈추기 때문!
  • R, B를 같이 움직이게 하거나 R, B를 따로 움직여도 상관없음! 겹치면 다시 백 하면 되니까!



풀이

구현 시 주의사항

💡 구슬이 동시에 움직이는 상황과 구슬이 겹치는 경우를 처리할 때 실수하기 쉽습니다. 각 방향별로 구슬의 우선순위를 정확히 파악해야 한다.
=> 움직일 때 마다 디버깅 추천!! (배열 출력해보아라)

💡 bfs(or dfs) -> move 함수 형태로 구현한다.
=> dfs의 경우 4방향 이동을 중복순열처럼 탐색하게 된다. (브루트포스)
=> move 함수의 경우: (1)’.’ 계속 이동, (2)’O’ 체크, (3)’R’,’B’ 겹치는지 순서로 진행!


핵심 구현 사항

  • BFS를 통한 최단 이동 횟수 탐색 or DFS를 통한 전체 탐색
    • 10번의 기울임까지 확인하므로 복잡도는 4^10*X 로 볼 수 있다.
    • X의 경우 구슬이 움직이는 칸으로 본다면, N*M=10*10=100 으로 크지 않다.
    • 따라서 DFS를 통해 전체 탐색을 해도 문제 없는 것이다. 범위를 작게 잡았으니까!
  • 구슬 이동 우선순위 처리
    • Red, Blue 구슬이 겹쳐지면 다시 “백” 하기 위해
  • 10회 초과 시 -1 반환
  • 파란 구슬이 구멍에 빠지면 실패


구슬 이동 처리

private static Pair move(int dir, Pair data) {
    Pair cur = new Pair(data.rx, data.ry, data.bx, data.by);
    int chk = checkPriority(cur, dir); // 이동 우선순위 결정
    //(1)'.' 계속 이동
    // ...
    //(2)'O' 체크
    // ...
    //(3)'R','B' 겹치는지
    // ...
    return cur;
}


우선순위 체크

public static int checkPriority(Pair p, int dir) {
    if(dir==0) { // 오른쪽으로 기울이기
        if(p.by<p.ry) return 0; // 빨간 구슬 먼저
        else return 1;          // 파란 구슬 먼저
    }
    // ... 다른 방향들
}



전체 코드 - BFS, DFS 둘 다

BFS 방식

public class 구슬탈출2_13460_bfs {
  static int N,M;
  static char[][] board;
  static int[] dx = {0,1,0,-1};
  static int[] dy = {1,0,-1,0};
  static Pair initRB;
  static int result=Integer.MAX_VALUE;

  static void bfs() {
    Queue<Pair> qu = new ArrayDeque<>();
    qu.offer(initRB);
    int cnt=0;
    while (!qu.isEmpty()) {
      int size = qu.size();
      cnt++;
      for (int s = 0; s < size; s++) {
        Pair cur = qu.poll();
        for (int i = 0; i < 4; i++) {
          Pair nxt = move(i, cur);
          if(nxt.priority==2) continue;
          if (nxt.priority==1) {
            result = cnt;
            return; //bfs라 어차피 최소값임. 바로 탈출하여 게임 종료하자.
          }
          qu.offer(nxt);
        }
      }
      if (cnt >= 10) { // 10회 초과부턴 무조건 -1임
        result=-1;
        break;
      }
    }
  }

  public static int checkPriority(Pair p, int dir) {
    if(dir==0) { // '->'
      if(p.by<p.ry) return 0; // 0:R
      else return 1;
    }
    if(dir==1) { // '아래'
      if(p.bx<p.rx) return 0;
      else return 1;
    }
    if(dir==2) { // '<-'
      if(p.by<p.ry) return 1; // 1:B
      else return 0;
    }
    if(dir==3) { // '위'
      if(p.bx<p.rx) return 1;
      else return 0;
    }
    return -1;
  }

  private static Pair move(int dir, Pair data) {
    //(1) '.' 끝까지 이동
    Pair cur = new Pair(data.rx, data.ry, data.bx, data.by);
    int chk = checkPriority(cur, dir); // 0:R, 1:B
    while (true) {
      //base condition
      if(board[cur.rx+dx[dir]][cur.ry+dy[dir]] != '.' && board[cur.bx+dx[dir]][cur.by+dy[dir]] != '.') break;
      if (board[cur.rx+dx[dir]][cur.ry+dy[dir]] == '.') {
        cur.rx+=dx[dir];
        cur.ry+=dy[dir];
      }
      if (board[cur.bx+dx[dir]][cur.by+dy[dir]] == '.') {
        cur.bx+=dx[dir];
        cur.by+=dy[dir];
      }
    }
    //(2) 'O' 인지 체크
    if (board[cur.rx+dx[dir]][cur.ry+dy[dir]] == 'O') {
      cur.priority = 1; //red
    }
    if (board[cur.bx+dx[dir]][cur.by+dy[dir]] == 'O') {
      cur.priority = 2; //blue
    }
    //(3) R,B 겹치면 해결
    if (cur.rx == cur.bx && cur.ry == cur.by) {
      if(chk==0) { // 'R'이 우선이라 'B'가 양보
        cur.bx -= dx[dir];
        cur.by -= dy[dir];
      }else if(chk==1) { // 'B'가 우선이라 'R'이 양보
        cur.rx -= dx[dir];
        cur.ry -= dy[dir];
      }
    }
    return cur;
  }

  public static void main(String[] args) throws IOException {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    board = new char[N + 1][M + 1];
    initRB = new Pair(0,0,0,0);
    for (int i = 0; i < N; i++) {
      String input=br.readLine();
      for (int j = 0; j < M; j++) {
        board[i][j]=input.charAt(j);
        if (board[i][j] == 'B') {
          initRB.bx=i; initRB.by=j;
          board[i][j]='.'; //어차피 R,B 겹치는건 따로 처리할거라 빈공간('.')로 표시
        }else if (board[i][j] == 'R') {
          initRB.rx=i; initRB.ry=j;
          board[i][j]='.';
        }
      }
    }
    //run
    bfs();

    //output
    System.out.println(result);
  }

  static class Pair {
    int rx; int ry; int bx; int by; int priority=0;
    public Pair(int rx, int ry, int bx, int by) {
      this.rx=rx; this.ry=ry; this.bx=bx; this.by=by;
    }

    @Override
    public String toString() {
      return "Pair{" +
          "rx=" + rx +
          ", ry=" + ry +
          ", bx=" + bx +
          ", by=" + by +
          ", priority=" + priority +
          '}';
    }
  }

}



DFS 방식

public class 구슬탈출2_13460_dfs {
  static int N,M;
  static char[][] board;
  static int[] dx = {0,1,0,-1};
  static int[] dy = {1,0,-1,0};
  static Pair initRB;
  static int result=Integer.MAX_VALUE;

  //중복순열과 유사
  static void dfs(int depth, Pair cur) {
    //base condition
    if (depth == 10 || result < depth) {
      return; // 10회까지 가능, 깊이가 result 보다 큰건 최소가 아니라서 필요가 없음
    }
    //recursion
    for (int i = 0; i < 4; i++) {
      Pair nxt = move(i, cur);
      if(nxt.priority==2) continue;
      if (nxt.priority == 1) {
        result = Math.min(result,depth+1);
        return;
      }
      dfs(depth + 1, nxt);
    }
  }

  public static int checkPriority(Pair p, int dir) {
    if(dir==0) { // '->'
      if(p.by<p.ry) return 0; // 0:R
      else return 1;
    }
    if(dir==1) { // '아래'
      if(p.bx<p.rx) return 0;
      else return 1;
    }
    if(dir==2) { // '<-'
      if(p.by<p.ry) return 1; // 1:B
      else return 0;
    }
    if(dir==3) { // '위'
      if(p.bx<p.rx) return 1;
      else return 0;
    }
    return -1;
  }

  private static Pair move(int dir, Pair data) {
    //(1) '.' 끝까지 이동
    Pair cur = new Pair(data.rx, data.ry, data.bx, data.by);
    int chk = checkPriority(cur, dir); // 0:R, 1:B
    while (true) {
      //base condition
      if(board[cur.rx+dx[dir]][cur.ry+dy[dir]] != '.' && board[cur.bx+dx[dir]][cur.by+dy[dir]] != '.') break;
      if (board[cur.rx+dx[dir]][cur.ry+dy[dir]] == '.') {
        cur.rx+=dx[dir];
        cur.ry+=dy[dir];
      }
      if (board[cur.bx+dx[dir]][cur.by+dy[dir]] == '.') {
        cur.bx+=dx[dir];
        cur.by+=dy[dir];
      }
    }
    //(2) 'O' 인지 체크
    if (board[cur.rx+dx[dir]][cur.ry+dy[dir]] == 'O') {
      cur.priority = 1; //red
    }
    if (board[cur.bx+dx[dir]][cur.by+dy[dir]] == 'O') {
      cur.priority = 2; //blue
    }
    //(3) R,B 겹치면 해결
    if (cur.rx == cur.bx && cur.ry == cur.by) {
      if(chk==0) { // 'R'이 우선이라 'B'가 양보
        cur.bx -= dx[dir];
        cur.by -= dy[dir];
      }else if(chk==1) { // 'B'가 우선이라 'R'이 양보
        cur.rx -= dx[dir];
        cur.ry -= dy[dir];
      }
    }
    return cur;
  }

  public static void main(String[] args) throws IOException {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    board = new char[N + 1][M + 1];
    initRB = new Pair(0,0,0,0);
    for (int i = 0; i < N; i++) {
      String input=br.readLine();
      for (int j = 0; j < M; j++) {
        board[i][j]=input.charAt(j);
        if (board[i][j] == 'B') {
          initRB.bx=i; initRB.by=j;
          board[i][j]='.'; //어차피 R,B 겹치는건 따로 처리할거라 빈공간('.')로 표시
        }else if (board[i][j] == 'R') {
          initRB.rx=i; initRB.ry=j;
          board[i][j]='.';
        }
      }
    }
    //run
    dfs(0, initRB);

    //output
    if(result == Integer.MAX_VALUE) result=-1;
    System.out.println(result);
  }

  static class Pair {
    int rx; int ry; int bx; int by; int priority=0;
    public Pair(int rx, int ry, int bx, int by) {
      this.rx=rx; this.ry=ry; this.bx=bx; this.by=by;
    }

    @Override
    public String toString() {
      return "Pair{" +
          "rx=" + rx +
          ", ry=" + ry +
          ", bx=" + bx +
          ", by=" + by +
          ", priority=" + priority +
          '}';
    }
  }

}

주관적인 생각의 풀이이므로 틀린 부분 지적은 언제나 환영합니다⚡

댓글남기기

참고