문제 11967. 불켜기(BFS 26번)

문제 링크

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

11967번: 불켜기

 

난이도 :  골드 2

 

문제 요약 설명

N X N개의 방이 있는 정사각형 모양의 헛간이 있다. 헛간에 있는 각 방은 (1, 1)부터 (N, N)까지 번호가 매겨져있다. 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

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

 

베시가 불을 켤 수 있는 방의 최대 개수를 출력하는 프로그램을 구하시오.(단, (1, 1)방도 포함한다)

입력

첫째 줄에는 N, M이 주어진다.

두번째 줄부터 M개의 줄에는 4개의 정수 x, y, a, b가 주어진다. 4개의 정수는 (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미한다.

입력 제한

• N(2 ≤ N ≤ 100)
• M(1 ≤ M ≤ 20,000)

입력 예제

// input
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

// ans
5

 

풀이 방식

해당 문제는 목적지를 찾아가는 문제가 아니다. 목표는 최대한 많은 방의 불을 켜는 것이다. 그렇기에 불을 많이 켤 수만 있다면 이미 방문한 방을 다시 지나가서 불을 켜야한다. 이런 특징 때문에 조금 다른 방식으로 bfs를 활용해야한다.

방문하지 않은 불켜진 방이 방문한 방과 인접해있는 지 확인해라.

베시는 어찌되었든 불켜진 방으로만 이동할 수 있다. 스위치로 켜진 방이 새로 생겼다면, 인접한 방이 방문한 방인지 확인하여 베시가 새롭게 불켜진 방으로 이동할 수 있는지 파악한다.

방문한 방과 연결되었다면, 연결되어 있는 모든 방문하지 않은 불켜진 방들을 전부 방문해라.

방문하지 않은 불켜진 방들은 아직 스위치를 누르지 않은 방들이다. 스위치를 눌러 불켜진 방들을 추가로 늘려야 되기 때문에 이 때 bfs를 활용해 연결된 모든 방들을 방문한다.

한 번 불을 켠 방은 다시 불을 켤 필요가 없다. 

이 문제는 불이 켜진 방을 최대로 만드는거지 불을 여러 번 켜는게 목적이 아니다. 한 번 켰다면 다른 방에서 해당 방에 불을 켜도 카운트에 넣지 않도록 조심한다.

정답 코드 링크

추후 업데이트

참고

항상 한 지점에서 퍼져나가는 bfs문제만 풀다가 여러 지점에서 시작하는 bfs문제를 처음 풀어보았다. 새로운 관점이니 머리 속에 기억해두자.