[JAVA] 백준 16928번 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

이 글을 쓰는 목적은 BFS 알고리즘을 한번 더 정리하고,

뱀과 사다리 게임 문제를 풀면서 놓쳤던 경우의 수를 기록해서 내 생각을 정리하고, 비슷한 실수를 반복하지 않기 위함이다.

 

위 문제는 그래프 탐색 알고리즘 중에서 BFS, Breadth-First Search 알고리즘에 해당하는 문제이다.

 

그래프란, 정점과 간선으로 이루어진 자료구조이다.

어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때, 어떠한 곳은 정점(vertex)이고, 무언가는 간선(edge)이 된다.

 

BFS 알고리즘은 너비우선탐색 알고리즘으로, 시작노드에서 인접한 노드부터 탐색하는 방법이다.

Queue 자료구조를 사용하여 인접한 노드를 차례대로 꺼내서 탐색할 수 있으며, 주로 가중치가 없는 그래프에서 최단거리를 찾는데 쓰인다.

 

DFS, Depth-First Search 알고리즘은 16964번 문제 후기에 기록했으니 넘어가겠다.

 

이 문제는 1부터 100까지의 숫자가 있는 보드판에 주사위를 굴리는데, 그 보드판에는 특정 번호에는 다른 특정번호로 이동하는 trap(?)이 있다. 더 높은 번호로, 더 낮은 번호로 이동할 수 있지만 하나의 번호 안에 이동하는 번호가 겹치지는 않는다. 

이동은 단방향 간선으로 이동한다.

 

이 문제를 풀 때, 한번에 통과하지 못하고 두번인가.. 틀렸는데 내가 생각하지 못했던 경우의 수를 잊어버리지 않기 위해서 위해 글을 남긴다.

처음에 38~39번째 줄에서 if(move[next]!=0 && boardMin[move[next]] == 0) 이라고 해서 틀렸었다.

- if(보드판 번호에서 순간이동(?)하는 번호에 걸리는 경우 && 그 경우에 아직 방문한 적이 없는 경우)

 

위 두 경우를 동시에 체크했었는데, 잘 생각해보니 그렇게 하면 else 일 때 걸러내지 못한 조건이 있었다.

 

1. 보드판에서 순간이동이 걸리지만, 방문한 적이 있는 경우

2. 보드판에서 순간이동이 걸리지 않지만, 방문한 적이 없는 경우

3. 보드판에서 순간이동이 걸리지 않지만, 방문한 적이 있는 경우

 

문제는 [1.보드판에서 순간이동이 걸리지만, 방문한 적이 있는 경우] 까지도 q 에 데이터가 들어가버린다!

 

이때는 q에 순간이동 하기 전의 숫자가 들어가버리게 된다.

2번에서 무조건 4번으로 가야 하면, 2번에는 머무르고 있을 수 없는데 2번에 머무르는 것으로 되어버리는 것이다.

 

그래서 && 조건으로 두었던 것을 if를 두번 써서 38번, 39번 두줄로 따로 빼주게 되었다.

앞으로 if 안에 && 조건을 하고 else를 쓰게 될 때는 모든 경우의 수를 잘 생각하고 주의해야 겠다.

 

그리고 위 조건을 좀더 단순하게 만들 수도 있었다.

36~45번 줄을 위와 같이 좀더 간편하게 수정해보았다.

제출했을때 위 코드도 통과되었다.