[BOJ]16946번: 벽 부수고 이동하기 4

문제: https://www.acmicpc.net/problem/16946

---

BFS + 아이디어가 필요한 문제입니다.

 

NM 값이 100만이므로 벽 갯수만큼 BFS를 돌려보면 시간초과가 납니다.

 

그러므로 BFS를 도는 횟수를 줄여야합니다.

 

해결한 아이디어는 다음과 같습니다. 

ex. 빈 칸끼리 붙어있는 값을 '컴포넌트'라고 하겠습니다.

 

1. 전체 BFS를 1번 돌면서 빈 칸으로 이뤄져있는 모든 컴포넌트 정보를 (컴포넌트번호, 컴포넌트 내 빈 칸 갯수) 저장합니다.

2. 1번 연산을 마친 다음에 모든 벽에 대해 벽이 있는 해당 칸과 인접한 4칸에 존재하는 컴포넌트 갯수를 더해줍니다. 1번에서 빈 칸 갯수 외에 '컴포넌트 번호'를 굳이 저장한 이유는 인접한 4칸을 탐색할 때 동일한 컴포넌트에 포함되는 빈 칸을 중복해서 저장하지 않기 위함입니다.

 

위와 같이 연산을 하면 O(NM)에 해결할 수 있습니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ16946.java