#11967 불켜기

출처:https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

 

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

 

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

풀이

bfs로 구현.

불이 켜져있는 곳을 방문하면 일단 다른 방 불을 모두 켜준다. 방문한 곳이 불이 켜져있지 않은 곳이여도 임시적으로 저장해야한다. 왜냐하면 불켜져있는 다른 방에서 방문대기는 한 상태이지만 아직 불이 켜져있지 않은 임시저장위치는 불을 켤 수 있기 때문이다. 그리고 방문을 하지 못하더라도 일단 불을 킬 수 있으면 결과값 카운트를 증가시켜야 한다.

 

코드