문제 : https://www.acmicpc.net/problem/14891
깨달은 것
- 디버깅을 할 때 눈으로 먼저하는 습관을 들일 것
- DFS와 BFS를 사용 할 시점을 잘 파악할 것
1. 디버깅 시 눈으로 먼저 해보자
이 문제를 처음 접했을 때는 DFS를 사용해야겠다고 생각했지만 생각하다가 BFS로 생각을 바꾸었다.
이유는, 톱니바퀴가 회전하면 즉시 주위에 영향을 미친다고 생각했기 때문이다.
하지만 하나의 톱니바퀴가 회전하면, 그 양옆에 있던 톱니바퀴들이 순차적으로 회전하는 것이다.
즉, 기준에서 양옆으로 귀납적으로 회전 조건들이 적용되는 것이다.
만약 회전하는 즉시 영향을 받은 다른 바퀴들도 회전하면서 주위에 영향을 준다면 분명BFS가 맞다.
이(나의 BFS를 사용해야한다는 생각이 틀렸다는 것을 깨닫는데에 오랜시간이 걸렸다)를 찾는데에 눈으로 흐름을 다시 읽어보다가 깨달았다. 눈으로 디버깅하면 나의 논리 흐름이 더 잘 보였다.
무엇보다도 문제를 잘 읽어야겠다.
2. DFS와 BFS를 사용 할 시점을 잘 파악할 것
앞서 1번에서 설명한 것과 같이 BFS를 사용 할 때와 DFS를 사용할 때를 잘 보자.
오랜만에 DFS를 사용해봤다.
중요하게 다가왔던 것은. DFS는 재귀로 구현 가능하며 재귀는 귀납적이다. 이때 귀납법은 n=0일 시는 다르게 적용 될 수 있음을 생각하자. 예를 들어, 이 문제에서는 사용자가 입력한 회전할 톱니 바퀴는 나머지들(양옆)이 모두 회전 된 후 회전을 한다. 즉, 한 방향으로만 회전을 하는 논리는 처음 회전한 톱니바퀴에 맞지 않다는 것이다. 그러므로 사용자가 회전시키는 바퀴는 main문에서 따로 회전을 시킨다.
오른쪽(왼쪽도 똑같이 생김)
void check_r(int gear_n, int turn)
{
if (gear[gear_n][2] != gear[gear_n + 1][6] && gear_n + 1 < 4)
{
check_r(gear_n + 1, !turn);
}
spin(gear[gear_n], turn);
}main문에서의 사용자가 지정한 바퀴의 회전
if (gear[gear_n][2] != gear[gear_n + 1][6] && gear_n + 1 < 4)
{
check_r(gear_n + 1, !turn);
}
if (gear[gear_n][6] != gear[gear_n - 1][2] && gear_n - 1 >= 0)
{
check_l(gear_n - 1, !turn);
}
spin(gear[gear_n], turn);