백준 2573 빙산

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

2573번: 빙산

풀이방법

1. check() 함수

각 칸이 몇 칸의 바닷물과 접해있는지 확인

 => v에 좌표와 줄어들 높이를 넣어주기

 

2. update() 함수

v에 들어 있는 정보로 각 칸의 높이를 업데이트 해주기

 

3. isSplited() 함수

BFS를 한 번 돌렸을 때, 모든 빙산의 조각(?)이 방문되지 않고 남아있다면 두 덩어리 이상으로 나눠진 것

=> total이라는 변수에 빙산조각의 개수를 담아넣고 q에 들어간 정점의 개수와 비교

     1) 같으면 한 덩어리

     2) 다르면 두 덩어리 이상

 

 

오답노트

1. 원래 check()내에서 빙산의 줄어든 높이를 바로바로 업데이트 했는데
  이렇게 하면 그 다음 칸도 영향을 받기 때문에 검사를 다 한 후에 한 번에 업데이트 해줘야 함

(나무재테크에서도 겪었던 문제 : 봄-여름을 한 번에 진행하면 그 다음 칸이 영향을 받는다)

 

2. 행과 열의 범위가 다름 => bfs 범위체크시 nx>n-1로 해서 틀림

 

 

 

http://colorscripter.com/s/bcwaJVG