[백준] No.2573 - 빙산 (C++)

문제

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

2573번: 빙산

 

풀이

meltDfs( ) : 주위의 블록을 확인하여, 0이라면 높이를 1씩 녹이고, 아니라면 재귀로 접근

r, c로 ice배열의 위치를 받아 Dfs로 위,양옆,아래의 네 방향으로 Dfs접근한다.

접근할 ice[nr][nc]가 0이 아니라면(빙산이라면)  visited[nr][nc]로 해당 위치를 방문했는지 확인한다.

방문하지 않았다면 그대로 meltDfs를 재귀호출 한다.

접근할 ice[nr][nc]가 0이라면 바다라는 뜻인데, 만약 visited[nr][nc]가 true라면 해당 블록은 빙산이 모두 녹아 0이된 경우이다.(바다는 항상 visited=false) . visited[nr][nc]가 false이고 ice[r][c]가 0 이상이면 높이를 1 줄여준다.

 

Dfs( ) : 연결된 빙산을 모두 방문

 

Routine( ) : 반복문을 돌며 meltDfs( )를 호출하고 Dfs( )로 빙산이 두 덩어리가 되는 시점을 반환

passed_year를 반복문을 돌 때마다 1씩 증가

함수들을 호출하기 전에 memset으로 visited를 false로 초기화 해주자.

먼저 Dfs()를 호출해 연결된 빙산의 덩어리의 개수를 cnt에 기록

만약 cnt=0이라면, 빙산이 없는 것으로 0을 반환

cnt>1 이라면, 두 덩어리 이상이 됐으므로 passed_year를 반환

cnt가 아직 1이라면, meltDfs를 ice[i][j] 가 0이 아닌(빙산인) 위치에서 호출한다.

 

소스코드

 

복기

nr,nc를 사용해야 하는 부분에 r,c를 넣어놔서 한참을 헤맸다..

 

블로그의 첫 글인데, 계속 gitgub에만 문제풀이 코드를 올리다 보니 풀이 방법을 작성하는 것도 불편하고

정리해야 할 이론과 같은 것들을 github에 올리기는 힘들어서 시작한다.

이전에는 문제만 풀 수 있도록 소스코드를 다른 사람이 이해하기 어렵게 작성했는데, 아무래도 블로그는 외부에 노출되다 보니 좀 더 코드를 이해하기 쉽도록 작성하는 습관을 들여야겠다. 풀이도 좀더 명확히 알 수 있도록 작성해보자!