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

 

<출처: https://www.acmicpc.net/problem/16946>

---

N, M 제한이 1000 이므로 벽 한 칸당 BFS를 돌아버리면 O(N^2*M^2)으로 시간초과가 납니다.

 

그러므로 단 한번만 O(NM)에 BFS를 돌려 모든 컴포넌트 정보를 얻어냅니다.

 

그 후에 벽에서 이동할 수 있는 칸 계산은 move = 1 + 4방향 컴포넌트의 갯수 합이 됩니다.

 

그래서 O(NM)만에 모든 벽 정보에 대해 벽에서 이동할 수 있는 칸을 계산할 수 있습니다.

 

단, 함정이 하나있다면,  

 

00000

00000

00100

00000

00000

 

이와 같이 벽을 둘러싼 컴포넌트가 동일한 형태일 때 4방향을 다 더해주면 중복이 날 것입니다.

 

그러므로 컴포넌트를 구할 때 하나의 컴포넌트가 다른 컴포넌트와 구분될 수 있도록 조치를 취해야 합니다,

 

저 같은 경우는 pair의 second 값을 이용했고, set을 통해 관리해주었습니다.

---

<코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16946.cc>