기로에 서다

문제 www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 풀이 모든 전구의 상태를 완전탐색한다면 $O(2^n)$으로 시간초과가 나기 때문에 다른 방법을 생각해봐야 합니다. 문제에서 구하는건 최소한으로 누르는 스위치의 개수이기에 스위치를 누르는 횟수를 줄이기 위해서 같은 스위치를 2번이상 누르지 않도록 해야합니다. 1. 스위치를 누르는 방향을 정해놓고 전구를 순회하면 한 번 누른 스위치는 다시 누르는 경우가 생기지 않으므로 방향을 정해놓고 진행합니다. ..