[c++] 백준 빙산(2573), BFS, 반례모음

문제 https://www.acmicpc.net/problem/2573

1,2,3년마다 빙산이 녹는 모습

• 해마다 위의 그림처럼 빙산이 녹습니다.
• 숫자를 제외한 빈 공간은 모두 0(바다)으로, 1년이 지나면 인접한 빙산을 녹이는데, 0의 개수만큼 녹습니다.
• 처음 빙산이 분리될 때, 몇 년이 지났는지를 출력하시오
• 분리되지 않고 모든 빙산이 녹을 때는 0을 출력.

 

반례

5 5 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0

4 4 0 0 0 0 0 3 1 0 0 1 3 0 0 0 0 0 1

5 7 0 0 0 0 0 0 0 0 3 3 2 3 3 0 0 4 0 4 0 3 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0

5 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

7 7 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 9 1 9 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 2

• 앞의 두 반례가 중요합니다.

 

풀이

• 기본적인 BFS를 사용하여 빙산을 찾고, 방문기록을 남깁니다. 동시에, 인접한 상하좌우에서 0(바다)를 찾고 그 개수만큼 빙산을 녹입니다. -> map[301][301]과 map_check[301][301]을 사용해서 update해줍니다. 여기서 map_check의 방문여부는 year(몇 년도가 지났는지)를 넣어줍니다. 
• 인접한 영역이 다른 빙산일 경우, 큐에 쌓아주고, 큐가 empty될 때까지 반복합니다. (일반적인 BFS)
• 이렇게 각 해마다 빙산의 경로를 BFS로 탐색함과 동시에 인접한 바다를 찾아서 빙산을 녹이고 업데이트 합니다.
• 그러나, 다음과 같은 조건을 고려해야 합니다.
  1) 빙산이 2개 이상으로 분리될 때
  2) 빙산이 분리되지 않고 모두 녹을 때
  3) 빙산이 지금까지 몇 개나 녹았고, 현재(올해) 남은 빙산은 몇 개인지
  4) 빙산의 경로 탐색시 현재 년도(year)보다 낮은 map_check 영역은 방문하지 않습니다.
• 위와 같은 조건을 고려하기 위해서 조금 까다로운 조건문을 잘 설정해주어야 합니다. 
  1) year이 지날 때마다 map에 있는 빙산들의 경로를 BFS로 반복적으로 탐색해야 하고, 그 과정에서 경로로 지나가는 빙산의 개수(count_ice)와 빙산이 녹아 없어지는 개수(erased_ice)를 세어줍니다. 
• 빙산의 개수(count_ice)는 빙산이 2개 이상으로 분리되었는지 체크를 위해, 맨 처음 빙산의 개수인(total_ice)와 동일한지 확인하고, 동일하지 않다면 빙산이 끊긴 것으로 반복문을 종료, year를 출력합니다.
• 빙산이 녹아 없어지는 개수(erased_ice)가 맨 처음 빙산의 개수인(total_ice)와 동일할 경우, 모든 빙산이 동시에 녹았으므로 0을 출력합니다. 그렇지 않을 경우 total_ice = total_ice - erased_ice 를 수행하여 현재 남아있는 빙산의 총 개수를 업데이트 해줍니다. 
• BFS에서는 올해(year)를 받고, map_check에 넣어주면서 빙산경로를 탐색하되, 이전 year에 방문한 빙산과 중복방문이 되지 않도록 조건처리합니다. 
• 굉장히 복잡해보입니다.. 맞습니다.. 제가 너무 어렵게 푼 것 같습니다. ㅠㅠ

 

코드

• x,y를 참조하여 bfs 시작좌표를 save해줍니다.
• erased_ice도 참조하여 갱신합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

알게 된 점

• 처음 문제를 볼 때 푸는 방법의 방향성은 알았지만, 이를 조건처리하는게 어려웠습니다. 조건문에 대한 연습이 부족한 것일까요? 풀면서 이렇게까지 조건처리를 해줘야 하나.. 싶었습니다. 
• 더욱 신중하게 코드를 작성해보자

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EB%B9%99%EC%82%B0(2573).cpp