백준 16946 벽 부수고 이동하기 4 C++

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

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

그냥 단순하게 bfs를 돌면 무조건 시간초과가 날 문제입니다. (100만 개 탐색을 100만번....)

 

그렇기 때문에 다음의 과정을 거쳤습니다.

 

1. 0으로 연결된 애들의 개수를 세준다. ex. 0 0 0 이런 맵이면 해당 위치는 연결된 0이 3개 이므로 3 3 3이 된다.

(그리고 이들은 모두 같은 영역이므로 2번 과정에서 카운트 시 중복되서는 안 됨)

2. 1 위치에서 상하좌우 돌면서 0이 나오면 그 위치의 값을 더한 값에 1을 더한 값 (자기 자신)이 답이다.

(단, 같은 영역의 0인 경우 또 더하면 안 된다.)

 

이러한 과정을 거치면 결국 0의 영역을 나누는 것은 최대 100만 번 탐색과 100만 번 값 복사, 1의 영역을 기준으로 탐색하는 것도 최대 100만번 이므로 초기 세팅을 비롯해도 100만번 x N 번 정도 연산이므로 시간초과에 여유롭습니다. (N은 문제에 주어진 N 아니고 그냥 적당한 값....) 

 

코드는 다음과 같습니다.