naturalspace   4년 전

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

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


portableangel   4년 전

오프라인 쿼리 + union-find 알고리즘으로 해결할 수 있을 것 같습니다.

건물을 쿼리대로 모두 부순 상태에서 출발, 역방향으로 쿼리를 풀며 추가되는 건물이 생길 때마다

추가된 건물 좌표의 상하좌우를 건물과 함께 유니온해주며, 쿼리당 답은 총 트리의 수로 세 주면 될 것 같습니다.

참고 : https://www.acmicpc.net/proble...

naturalspace   4년 전

portableangel 님 답변해주셔서 너무 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.