안녕하세요. 제가 아는 분이 이런 문제를 어떻게 푸냐고 물어보시더라구요.

2667번: 단지번호붙이기

기본적으로는 이런 BFS류의 문제인데 문제는 가로, 세로의 크기가 최대 500 이고요.

한번 세고 끝나는게 아니라 (위 문제로 따지면) 건물의 일부분이 파괴되고 다시 건물이 몇개인지 세야하는데

이 질의가 10만번이고, C기준 제한시간 1초, 메모리 256mb 정도라고 하네요.

예를 들어 가로, 세로 3, 3 이 데이터로 주어지고 그 다음 3행3열 데이터가 주어지고요.

그다음 질의의 갯수 3 이 주어지고 그 아래 3, 7, 5가 주어 진다고 하면 

처음에는 숫자 그룹을 한덩이(한 아파트)라고 볼 수 있고요. 질의대로 3을 제거하고나서 다시

그룹갯수를 세는거에요. 그러면 3이 7과 나머지 그룹을 갈라놓기 때문에 2 그룹이 되니 2를 출력합니다.

그다 음 7을 제거하고 나면 그룹이었던 7 외딴 한덩이가 제거되니 그룹이 1개가 되서 1을 출력합니다.

그 다음 5를 제거하면 (8)과 (1,2) 가 남으니 2덩이가 되니 2를 출력합니다. 그래서 답은

2 1 2 라고 출력하면 되는데요. 이 문제가 아무리 생각해도 제한시간내 답이 안나오는데

이런 로직을 빠르게 처리할 수 있는 알고리즘이 존재하는것인지 궁금합니다. 고수님들 도와주세요.

3 3

5 3 7

8 3 3

5 1 2

3

3 7 5