파일 업로드

조명 켜기

  • 너비 우선 탐색
  • 그래프
  • 큐
  • 집합
  • 리스트
profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

N x N 크기의 집이 있으며, 각각의 방은 그리드 좌표로 표현됩니다. 

동주는 (1, 1) 위치에서 시작하여 조명이 켜져 있는 방만을 통해 상하좌우로 인접한 방으로 이동할 수 있습니다. 

일부 방에는 스위치가 설치되어 있어, 해당 방의 스위치를 이용하면 다른 방의 조명을 켜거나 끌 수 있습니다. 

동주가 이동하며 켤 수 있는 방의 최대 개수를 구해주세요.

💻 입력

- 첫 번째 줄에는 집의 크기 N과 스위치의 개수 M이 공백으로 구분되어 주어집니다. (2 <= N <= 100, 1 <= M <= 20,000)

- 이후 M 줄에 걸쳐, 네 개의 정수 x, y, a, b가 공백으로 구분되어 주어집니다. 이는 (x, y) 위치의 방에 있는 스위치를 통해 (a, b) 위치의 방의 조명을 조작할 수 있다는 것을 나타냅니다. 하나의 방에는 여러 개의 스위치가 있을 수 있으며, 여러 스위치가 같은 방의 조명을 조작할 수 있습니다.

🖨️ 출력

- 동주가 조명을 켤 수 있는 방의 최대 개수를 출력합니다.

💻 예제 입력 1
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1
🖨️ 예제 출력 1
5
💡 힌트

여기에서, 베시는 (1,1)(1,1)에서 스위치를 사용하여 (1,2)(1,2)와 (1,3)(1,3)의 방 불을 켤 수 있습니다. 

그런 다음, 그녀는 (1,3)(1,3)으로 걸어가서 (2,1)(2,1)의 방 불을 켤 수 있고, 거기에서 (2,2)(2,2)의 방 불을 켤 수 있습니다. 

(2,3)(2,3)의 스위치는 그녀에게 접근 불가능하며, 이는 그 방에 빛이 없기 때문입니다. 따라서 그녀는 최대 5개의 방 불을 켤 수 있습니다.

출처: USACO 2015 December Contest, Silver Problem 1. Switching on the Lights