asd0113   2년 전

해당 코드의 알고리즘은 BFS방식으로 시도하였습니다.

알고리즘은 다음과 같은 방식으로 진행합니다.


1. queue의 front부분에서 위치 정보 하나를 얻어서 위, 아래, 오른쪽, 왼쪽으로 공을 굴립니다.

2. 공을 굴리는 방식은 각 방향으로 공의 위치를 이동시킨 후, 공이 겹쳤을 경우 원래의 공 위치를 고려하여 다시 공을 이동시켜줍니다.

    (공이 겹친 부분은 코드에서 // overlaped 아래 부분을 참고하시면 됩니다.)

3.  빨간 공이 구멍이 들어갔을 경우 성공 플래그를 true 해주고, 파란 공이 구멍에 들어갔을 경우 실패 플래그를 true로 해줍니다.

4. 실패 플래그가 false일 경우에 한해서 성공 플래그가 true일 경우 원래 위치까지 도달한 경우의 step의 +1의 값을 return하고, 그렇지 않을 경우 다음 경우를 위해 위치 정보를 queue에 넣습니다.


1~4를 반복합니다.


나와있는 테스트 케이스는 모두 맞았으며, 11번 째 step까지 수행하는 테스트 케이스까지 만들어 보았지만 실패했습니다.

10 10
##########
#BR......#
#......#.#
#........#
######.###
#....#...#
#....##..#
#........#
#......O##
##########

예를 들면, 해당 케이스로 시도해 보았으며, 11번 째 시도를 할 경우 실패합니다.



그래서 다른 테스트 케이스가 도저히 떠오르지 않아 질문 게시판에 도움을 요청하고자 합니다.


감사합니다.

smtsyh   2년 전

이 테스트 케이스는 어떨까요

제가 해본 결과로는 7이 맞는것 같은데..

10 10
##########
#R.....#B#
#........#
#........#
#........#
#........#
#........#
#.....#..#
#....#O..#
##########

asd0113   2년 전

smtsyh

감사합니다. 해결되었습니다. :)

틀린 부분이 overlaped 부분이 틀렸었네요.

이전에 같은 줄에서 떨어져있던 상태에서 공을 굴렸을 때 겹친 것을 제대로 체킹을 못했네요.

감사합니다.


myth   2년 전

위에 알려주신 테스트 케이스는 아무리 봐도 파란색 공이 구멍으로 들어 가서 -1 이 되는 것 같은데요,

어떻게 7이 나오는지 간단한 설명 부탁 드립니다~

sukwoo0711   2년 전

@myth

1.오른쪽

2.아래

3.오른쪽

4.위

5.왼쪽

6.아래

7.왼쪽


이 순으로 들어가면 됩니다

댓글을 작성하려면 로그인해야 합니다.