(JAVA) 백준 10711번 : 모래성

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

10711번: 모래성

 

 

시간초과 때문에 꽤나 애먹었던 문제..

 

 

 

핵심 키워드는 이거다.

 

"모래성이 아닌 빈 모래를 활용하라."

 

 

 

BFS, DFS, Deque, 2중 for문 등등

 

여러 방법을 동원해봤지만

 

테스트케이스는 통과하는데 시간은 초과되는 문제가 계속 일어났다.

 

 

 

그러던 중, 

 

번뜩 떠올랐다.

 

 

 

 

"굳이 파도 한 번마다 모래성 주위 8방향을 탐색하며 갯수 셀 필요가 있을까?"

 

"모래성은 어차피 줄어들고, 빈 모래는 늘어나니까."

 

 

 

"BFS를 사용해서 빈 모래 근방 모래성들 크기를 1씩 떨어뜨리면 되지 않을까?"

 

"어차피 한 번만 빈 모래 사용하면 이후에는 굳이 사용할 필요가 없지. 빈 모래는 다시 찾지 않아도 되니."

 

 

저 4문장을 보고 나면

 

대충 알고리즘과 해결방법이 떠오를 것이다.

 

 

 

그렇지만 

필자가 설명을 잘 못한 것일수도 있기에

 

필자의 매커니즘과 소스코드를 첨부하겠다.

 

매커니즘

---

1)  입력 값 int 2차원 배열에 입력

 

 

2)  입력 값 중 빈 모래 발견 -> 빈 모래의 x ,y 좌표 값 별도 Queue에 담기

*** 당연히 x, y 좌표를 담는 별도 Class를 생성해야 함

 

 

3)  빈 모래 empty 까지 Queue에서 꺼내기

*** 중요한 것은 처음에 queue의 크기를 가져와야 한다. 파도가 치는 시간을 파악해야 하니.

*** 그래서 empty 까지 계속 꺼낼 때 마다 count하면서 처음에 저장한 queue의 크기와 비교한다.

같아질 경우에는 파도가 한번 휩쓸고 지나간 경우이므로 다시 queue의 크기를 가져오고 empty 까지 위 과정을 반복 진행한다.

 

 

4)  꺼낸 빈 모래 주위 8곳 크기 -1 진행

 

 

4 - 1)  주위 크기 중 0이 되는 모래가 있으면 빈 모래(. => 필자는 -1로 정의) 로 바꾸고 빈 모래 좌표 Queue에 넣기

 

 

5)  위 과정을 Queue가 empty 될 때 까지 반복 => empty는 수렴한 경우이므로 종료 후 경과 시간 출력

 

 

 

소스코드

---