11967. 불켜기#
관찰#
문제는 격자 형태의 방에서
- 스위치를 통해 다른 방의 불을 켤 수 있고,
- 불이 켜진 방만 이동 가능할 때,
결국 불을 켤 수 있는 방의 최대 개수를 구하는 것이다.
실제로 방 크기 \( N \)가 크지 않아,
불을 하나 켤 때마다 전체 맵을 다시 탐색하는 방식도 충분히 되겠다는 생각이 들었다.
불을 켤 때마다 BFS를 다시 돌려도 시간 제한(2초) 내에 들어가는 수준이다.
다만, 더 최적화 하고 싶어
“한 번의 BFS로 끝낼 수 없을까?” 를 고민했다.
구상한 핵심 로직은 다음과 같다.
- 큐에서 방 하나를 꺼낼 때마다, 그 방에 연결된 스위치를 모두 확인해 새로 불이 켜지는 방들을 갱신한다.
- 새로 불이 켜진 방 중에서, 이미 방문 가능한 영역(상하좌우)에 붙어 있는 방이라면
그 즉시 큐에 넣어 다음 탐색 대상으로 만든다. - 이렇게 하면 “불을 켜는 과정”과 “이동 가능한 영역을 넓히는 과정”을
단일 BFS 루프 안에서 동시에 처리할 수 있다.
이 방식으로 구현하면,
불을 켜기 위해 전체 지도를 반복해서 재탐색할 필요 없이
한 번의 BFS로 탐색과 스위치 처리를 함께 수행할 수 있다.
시간 복잡도#
N: 방의 한 변 길이, M: 스위치의 개수
그래프 형태의 BFS의 시간복잡도는 \( O(V+E) \)로 알려져 있다.
- 격자는 \( N \times N \) 개의 방이 있으므로, 정점 수 \( V = N^2 \) 인 그래프로 볼 수 있다.
- 상하좌우 인접 간선은 정점당 최대 4개이므로 \( E = O(N^2) \) 정도이다.
1) 단순 접근#
불을 켤 때마다 전체 맵을 다시 BFS로 훑는다면,
- 한 번 BFS: \( O(N^2) \)
- 이 과정을 여러 번 반복 → 최악에는 \( O(N^2) \) 번 가까이 돌아
- 대략 \( O(N^4) \) 수준까지 늘어날 수 있다.
\( N \le 100 \) 이라면, \( N^4 = 100^4 = 10^8 \) 정도로,
1초에 1억 번 연산 정도를 가정하면 통과 가능한 수준이다.
2) 최적화 접근#
최적화된 풀이에서는
- 각 방을 최대 한 번만 큐에 넣어 탐색하고,
- 각 방에서 자신에게 연결된 스위치 리스트를 한 번만 순회한다.
따라서 전체 시간 복잡도는
- 격자 BFS: \( O(N^2) \)
- 스위치 처리: \( O(M) \)
를 합친 \( O(N^2 + M) \) 로 정리할 수 있다.
이 문제의 조건인 \( N \le 100 \), \( M \le 20\,000 \)을 고려하면,
충분히 여유 있는 시간 안에 동작한다.