백준 13459 구슬 탈출

https://www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

문제

• N x M 배열이 주어진다.
• 배열안에는 구멍('0'), 빨간구슬('R'), 파랑구슬('B')가 주어진다.
• 구슬은 중력을 이용해서 이리 저리 굴려야 한다.
  • 이리저리 = 왼쪽, 오른쪽, 위쪽, 아래쪽 기울이기
• 빨간색 구슬이 구멍이 빠지면 성공이다.
  • 조건1) 빨간 구슬과 파란 구슬이 같이 빠지면 실패
  • 조건2) 빨간 구슬과 파란 구슬은 같은 칸에 있으면 안된다.
  • 조건3) 10번 이하로 빼내야 한다.

풀이

• 빨간 구슬과 파란 구슬은 동시에 관리해야한다.
• 바깥 행과 열은 벽('#)으로 막혀있어서 범위를 체크해줄 필요가 없다.
• 만약 같은 칸에 있을 경우!!
  • 빨간 구슬과 파란 구슬의 각각의 이동거리를  계산하여 더 많이 이동한 쪽을 이전 위치 한 칸 돌려준다.

 

주요 메서드

• 매개변수
  • r : 현재 x좌표
  • c : 현재 y좌표
  • dist : 움직인 거리
  • d : 방향(4방향)

   private static Move move (int r, int c, int dist, int d){
        int rr =r, cc= c;
        if (graph[rr+dx[d]][cc+dy[d]] != '#')
        {
            rr = rr + dx[d];
            cc = cc + dy[d];
            dist ++;
        }
        return new Move(rr,cc,dist);
    }

 

• 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우

 // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
        // 빨간 구슬이 더 많이 이동했을 경우
        if(nRed.dist> nBlue.dist) {
            // 이전 위치로
            nRed.r -= dx[d];
            nRed.c -= dy[d];
        } else {
            nBlue.r -= dx[d];
            nBlue.c -= dy[d];
        }
    }

• bfs 로직

 while(!q.isEmpty()) {

            int size = q.size();
            while(size-- > 0) {
                Turn now = q.poll();

                // 4방으로 장난감을 기울여보자.
                for (int d = 0; d < 4; d++) {
                    // 빨간 구슬 이동
                    nRed = move(now.Rr, now.Rc, 0, d);
                    // 파랑 구슬 이동
                    nBlue = move(now.Br, now.Bc, 0, d);

                    // 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
                    if(graph[nBlue.r][nBlue.c] == 'O') continue;
                    // 빨간 구슬만 구멍에 빠질 경우
                    if(graph[nRed.r][nRed.c] == 'O') {
                        return 1;
                    }

                    // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
                    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
                        // 빨간 구슬이 더 많이 이동했을 경우
                        if(nRed.dist> nBlue.dist) {
                            // 이전 위치로
                            nRed.r -= dx[d];
                            nRed.c -= dy[d];
                        } else {
                            nBlue.r -= dx[d];
                            nBlue.c -= dy[d];
                        }
                    }

                    // 이미 시도해봤던 상태라면 pass
                    if(visit[nRed.r][nRed.c][nBlue.r][nBlue.c]) continue;

                    visit[nRed.r][nRed.c][nBlue.r][nBlue.c] = true;

                    // Queue에 추가
                    q.add(new Turn(nRed.r, nRed.c, nBlue.r, nBlue.c));
                }
            }

            // 10번 이하로 성공할 수 없다면
            if(++time > 10) return 0;
        }
        return 0;
    }