[백준 / BOJ] 5827 What's Up With Gravity

문제

출처 : https://www.acmicpc.net/problem/5827

5827번: What's Up With Gravity

캡틴 보비디안은 그녀의 선원 닥터 비팔로를 찾으러 모험을떠난다.

캡틴 보비디안이 도착한 세계는 N*M그리드로 표현되어있으며, 해당 세계는 다음과 같은 룰을 따른다.

 

1. 만약 캡틴 보비디안의 아래(보비디안의 위치가 y,x라 할때, 보비디안의 아래란, y+1,x 를 뜻한다.)에 어떠한 바닥도 없다면, 캡틴 보비디안은 바닥으로 떨어진다. (벽(#)을 만날때까지 반복한다고 생각하면 된다.)

 

2. 만약 캡틴 보비디안이 N*M그리드 밖으로 나가면, 그녀는 우주로 날아가며, 모험은 실패로 끝난다.

 

3. 캡틴 보비디안의 아래에 벽(#)이 있다면, 그녀는 다음 세가지 행동을 할수있다. 

- 중력 반전시키기 (중력을 반전시킬경우 캡틴 보비디안은 반전된 중력에따라 벽을 만날때까지 떨어진다.)

- 왼쪽으로 이동하기 (단, 이동위치에 벽이있다면 이동하지못한다.)

- 오른쪽으로 이동하기 (단, 이동위치에 벽이있다면 이동하지못한다.)

 

위 행동을 적절히 시행해서 닥터 비팔로를 찾으려한다. 닥터 비팔로를 찾는 최소 중력반전횟수를 구하는 문제다.

찾지 못할경우 -1을 출력한다.

---

풀이

오랜만에 디버깅 지옥에 빠진 문제다.

BFS알고리즘을 사용해 풀었다

 

알고리즘은 다음과 같다.

 

1. 캡틴 보비디안의 위치를 확인한다.

- 해당 위치에 도달한 최솟값이 아니라면 continue

2. 캡틴 보비디안의 행동을 수행한다.

- 현재위치에서 중력을 반전시킨결과를 queue에 집어넣는다. (이때, 중력을 반전시키고 중력에따라 떨어트려야한다. 떨어트리는 중에도 닥터 비팔로를 만날수있다는점에 유의하자.)

- 현재위치에서 (y,x+1) (y,x-1)로 이동시킨 결과를 queue에 집어넣는다.

 

위 과정을 수행하면 답이나온다.

(알고리즘은 쉽지만 디버깅은 그렇지 않다)

 

문제를 풀면서 주의할점은 다음과 같다.

캡틴 보비디안이 공중에서 시작했다면, 보비디안을 바닥으로 떨어트려야함에 주의하자.

 

캡틴보비디안의 시작지점에 대한 언급이 하나도 없어서(내가 해석을 못한걸수도있다.) 보비디안과 비팔로 시작지점 잡는것에대해 계속 제출해보면서 확인했다. 이유는 다음과 같은데,

1. 캡틴보비디안이 중력이 반전된 상황에서 시작하는 경우가 입력으로 주어지는가?

예를들어, 다음과 같은경우 -1을 출력해야하는지 0을 출력해야하는지와 같은 이유다..

5 5

#####

#C. . D

#. ###

#. ###

#. ###

중력이 반전된 상태로 시작할수있으면 0이출력되고 아니라면 -1이 출력되어야한다.

 

2. 닥터 보비디안이 공중에있는경우가 입력으로 주어진다면, 닥터보비디안도 중력의 영향을 받아 떨어트려야할까?

(사실 문제에 닥터보비디안이 중력의 영향을 받는다는 내용이 없어서 생각 안해도 되긴했을거같다.)

 

수많은 디버깅 결과! 그냥 캡틴 보비디안이 공중에서 시작했다면, 보비디안을 바닥으로 떨어트리기만 하면된다

 

문제를 풀면서 만든 테케는 아래와 같다.

7 7
#######
#.....#
#..#..#
#...D.#
#.....#
#C....#
#######

출력 1

 

5 5
#####
#...#
#.#D#
#C###
#####

출력 : 2

5 5
#####
#...#
#...D
#C..#
#####

출력 : -1

5 5
#####
#...#
#...D
#C...
#.###

출력 -1

 

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/5827%20What's%20Up%20With%20Gravity/Main.java

devxb/JJUNalgo