백준 2452 자바 - 그리드 게임 (BOJ 2452 Java)

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

 

어려웠음.. 2일이나 걸렸음..

기본적인 로직은 아래와 같이 잡음

1. 각 구간은 어차피 동시에 움직이므로 동일 색상으로 된 구간 전체를 하나로 생각함

2. 그러면 배열 전체에 대한 bfs에서, 그래프에 대한 bfs로 압축시킬 수 있음. bfs로 생각한 이유는 결국 각 구역별로 색상이 변하는거니 한칸만 잡고 계속 변경한다고 보면
결국 가장 먼 구역까지의 bfs라고 생각했음. 즉, 구역을 나누고 각 구역별로 모든 지역까지 bfs를 때린다음 그 횟수가 가장 적은게 답이라 생각함.
즉, 
3 3
1 0 0
1 0 0
0 1 1

이러한 입력에 대해 구간을 나눠서 숫자를 붙임. (이게 필요할꺼라 생각해서 한건데 하고보니 이게 flood fill 인듯함)
0 1 1
0 1 1
2 3 3
그럼 9개짜리 배열에서 정점 0,1,2,3개에 edge 0-1, 0-2, 1-3, 2-3 만 판단하면 되는것으로 압축이 됨.
-> 여기 로직까지가 주석기준으로 set div num과 make graph 까지임.

3. 이후 그냥 graph에 대한 bfs로직만 돌리면 된다!고 생각했고 여기까진 에이 뭐야 그렇게 안어렵네! 라고 생각했는데 당연하게 시간초과가 났음.
실제로 돌려보니 10초는 기본으로 넘어감 ㅋㅋ 생각해보니 아래와 같은 케이스 등에 대한 처리가 필요했음.
100 100
1 0 1 0 ...
0 1 0 1 ...
...
차라리 틀렸습니다. 가 떴으면 에이 이 난이도는 내 수준으론 못하나보다 하고 넘어갔을텐데..
시간초과라서 댐벼봤음. 결국 시간초과 잡는데 2일걸림.
코드적으로도 최대한 시간 줄어들게 변경하고 (예를들어 edge도 원랜 그냥 배열이었는데, hashmap<arrayList>로 변경하고..
심지어 Iterator로 받으면 안되고, for-each로 해야 통과된다던지..)
 flood fill로 채워둔 배열과 그래프를 키값(?)을 div로 잡고 배열의 중간지점부터 돌림. (tc를 많이 돌려보니 결국 답은 중간지점 근처에서 나옴)
그래도 시간초과나서 cutCnt라는걸 넣어서 중앙 일부 지역만 보게함.
-> 수학적으로 증명은 못하겠으니 사실상 그냥 백준에서 AC 뜰때까지 중앙 일부 지역을 확대하면서 돌려봄 ㅋㅋ

2초제한이니 자바론 5초제한인데 4.8초정도니 진짜 딱 턱걸이했음.
나중에 실력 좋아지면 좀더 줄여봐야지..

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2452.java