(JAVA) 백준 11967번 : 불켜기 -- [BFS]

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

11967번: 불켜기

 

 

 

이 문제의 핵심은 위에서 칠한 부분입니다.

 

각 방에서 상하좌우로 이동이 가능한데, 중요한 것은 불이 켜져있는 방으로만 들어갈 수 있다는 것.

 

그리고 문제에서 원하는 값은

불을 켤 수 있는 방의 최대 개수입니다.

 

즉, 최대한 많이 이동하여 방을 방문해서 불을 많이 켜야합니다.

 

유의사항은

 

1) 시작점은 무조건 불이 켜져있다. 개수 + 1

2) 방문하지 못하는 방이더라도 불을 키면 해당 방을 count할 수 있다. 개수 + 1

 

중요한 것인

3) 각 방에서 킬 수 있는 방은 인접한 방이 아니라 거리에 상관없는 방도 가능합니다.

 

이는 지금까지 지나왔던 방들 중에 인접한 방에 불이 켜질수도 있다는 것입니다!!

 

 

그렇기 때문에

단순히 BFS 알고리즘 한 번 수행해서 최대 방의 개수를 얻을 수도 있지만

BFS 알고리즘 중 지나왔던 방 근처에 불이 켜지면 그쪽으로도 방문해야하기 때문에 이를 해결하기 위해 

 

불켜진 방 중 아직 방문하지 않은 방이 없을때까지 (1, 1) 에서 시작하는 BFS 알고리즘을 반복해서 수행합니다!

 

다음으로,

그래프를 그리기 위해 기존 문제들은 보통 하나의 Vertex에서 다른 하나의 Vertex로 이동하기 때문에 1차원 ArrayList 배열을 활용했다면

 

여기서는 (x, y) -> (x, y) 이동이기 때문에 2차원 ArrayList 배열을 활용하여 Graph를 그립니다.

 

 

마지막으로,

BFS 순회를 위해 방문여부를 체크하는 배열을 만들어 중복 방문을 방지합니다.

 

 

자세한 사항은 아래 소스코드를 참고하시면 될 것 같습니다.

 

감사합니다!

 

 

소스코드

---