1) 문제를 분석해보자
일단 빨간 구슬이 구멍에 빠지도록 하는게 첫 번째 목표이다. 이 때 떠오른게 예전에 길 찾기 문제에서 썼던 DFS랑 BFS였다.
그 문제하고 다른 점은, 파란 구슬도 있으며 파란 구슬은 구멍에 빠지면 안 되고, 한 칸씩 공이 움직이는게 아니라 장애물이나 구멍을 만날 때까지 한 방향으로 계속 굴러간다는 것이었다.
처음에는 아무 생각 없이 DFS를 썼는데, DFS 사용하면 문제점이, 오른쪽으로 한 번만 굴러가면 정답이 나오는데 다른 쪽으로만 쭉 파다보면 돌고 돌아서 더 긴 루트로 답을 찾게 된다. 게다가 공이 한 칸씩 움직이는 게 아니라 한 번에 여러 칸을 움직일 수 있다보니까 오히려 BFS가 답을 더 빨리 찾는 것 같다. 공부를 더 해봐야 정확한 이유를 알 수 있을 것 같다.
2) 첫 시도
BFS로 알고리즘 바꾸고 나서 문제에 올라와있는 테스트 케이스는 통과했는데 자꾸 답이 틀렸다고 해서 디버깅을 해보았다. 여기서 찾아낸 사소한 실수는:
- case문에서 break 안 써서 중복됨
- 빨간 공이 안 움직일 때만 고려했는데 생각해보니 빨간 공은 안 움직여도 파란 공이 움직이면 유효한 것이므로 보드를 기울였는데 빨간 공과 파란 공 둘 다 제자리에 머물러 있으면 무시하는 걸로 코드 수정
- 변수 명 틀림… 등등이었다.
3) 대략적인 알고리즘
우선 enum type으로 방향을 위(0),아래(1),오른쪽(2),왼쪽(3) 으로 각각 정의하고, 각 방향에 따라 보드를 기울였을 때의 공의 위치를 계산하는 함수를 짰다. 이 때, 특정 방향으로 공이 굴러갈 때 장애물의 유무와 구멍의 유무만 고려하도록 하였다. 가령, 앞에 파란 공이 있는 지 이런거는 고려 안 하고 단지 공이 굴러갔을 때 어디에서 멈출지만 계산하여 그 좌표값을 리턴하도록 하였다.
먼저, 처음에 파란 공에 대해서 계산해주고, 만약 구멍을 만나서 found 변수 값이 1이 되었으면 실패한 것이므로 무시하고 다른 방향으로 넘어간다. (처음에 이때 found 값 다시 0으로 안 바꿔줘서 이거 찾아서 수정하느라 애를 먹었다)
그 다음 빨간 공에 대해서도 똑같은 함수로 계산해준다. 이 때, 빨간공이 구멍을 만나 found 값이 1이 되었으면 성공! 루프를 빠져나가고 결과를 출력한다.
만약 둘 다 구멍을 안 만났으면, 보드를 기울였는데도 둘 다 움직이지 않고 제자리에 있는지(길이 막혔는지) 확인해 준다. 이 경우에도 무시하고 다른 방향으로 넘어간다.
만약, 빨간 공과 파란 공 둘 다 같은 함수 리턴 값이 같다면(같은 위치로 굴러간다고 결과가 나왔으면), 이 둘이 같은 행 혹은 열에 있었다는 뜻이므로 둘 중 하나의 좌표 값을 수정해줘야 한다.
예를 들어, 빨간 공이 파란 공 왼쪽에 있었고 보드를 오른쪽으로 기울였다면 빨간 공의 새로운 위치는 파란 공의 위치에서 한 칸 왼쪽이어야 한다. 이를 switch문 사용해서 기울인 방향과 원래 빨간 공,파란공의 위치에 따른 케이스별로 처리해줬다.
이렇게 해서 두 공의 새로운 위치 값을 찾아주었다면 이를 큐에 삽입하고 큐에서 다음 값을 꺼내서 똑같이 반복해준다.
4) 어려웠던 점
- 다양한 케이스를 일일히 고려하고 코드를 짜는 게 어려웠다
- 몇 번의 시도만에 성공하는지 값을 출력하려면 bfs 트리 레벨을 기록해야 하는데 이걸 어떻게 할 지 고민하다가 결국 큐에 삽입하는 struct 타입에 bfs 레벨을 기록하는 새로운 변수를 추가해주고 매번 큐에 새로 삽입할 때 마다 이 값을 1씩 증가시키도록 하였다. 이렇게 되면 구멍을 만났을 때 현재 빨간 공의 레벨이 몇 번 시도했는지를 나타낸다.
/** position of each ball **/
typedef struct _pos{
int x;
int y;
int level;
}pos;