https://www.acmicpc.net/problem/31782
문제요약
- 2000*2000 지도가 주어짐. 정상/저체온증
- 낮이되면 저체온증->정상 가능. 상하좌우 2명 이상 정상이면 가능. 충분히 반복 가능
- 밤이 되면 최대 K 명 정상->저체온증
- 충분한 시간이 지나도 낮에 정상을 유지할 수 있는 사람 구하기
접근법
- 처음 문제를 접하면 뭘해야할지 모름. 특히 밤에 최대 K 명 저체온증 처리가 어려움
- 일단 주어진 입력으로 낮을 진행해봄 => 직사각형 영역이 여러개 만들어짐
- 밤에 직사각형 영역의 한 변을 몽땅 저체온증으로 바꾸면 낮에 복구가 안됨
- 한변을 몽땅 바꾸지 않으면 낮에 복구가 가능함 (ㄱ, ㄴ 모양에서 빈 곳이 복구가 됨)
- 즉 정상으로 만들어진 직사각형의 한 변이 K보다 큰지 작은지 판단하면 됨
- 낮의 진행은 BFS를 이용했음
- 정상을 queue에 넣음
- 정상 주변 저체온증에 +1 씩 카운트를 해줌
- 카운트가 2 이상이 되면 -> 정상으로 바꾸고 -> 새롭게 queue에 넣음
newbieski