백준 2638 자바 - 치즈 (BOJ 2638 Java)

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

 

  안쪽에 빈 공간은 공기에 접촉하지 않은 것으로 가정하므로, 단순히 배열 전체를 확인하며 공기부분의 상하좌우를 파악하면 안됨. 치즈가 존재하지 않는 외곽에서 시작해서 (코드에선 (0, 0)에서 시작함) dfs나 bfs를 돌려 인접한 공기들로 탐색하면서 인접한 치즈를 확인해야 함.

 

  구현은 사실 간단했음. 반복문 돌리면서 매번 다음의 처리를 해줌.

 

1. 매번 (0, 0)부터 dfs 돌리면서 상하좌우로 접한게 치즈라면 해당 치즈 부분의 값을 +1 해줌. 접한게 공기라면 그쪽으로 dfs 계속 진행함. (42 line)

2. 치즈인 부분의 갯수를 세줌 (cnt 변수)

3. 공기와 접한 부분이 2면 이상이라면 (코드상으로는 따로 배열 만들기 귀찮아서 0인게 공기, 1인게 치즈였고 공기와 닿았다면 +1을 시켜줬으므로 배열의 값이 3이상이면 2면 이상 닿은 것) 치즈를 제거하고 공기로 변경함 (48 line)

4. 횟수(answer 변수)를 1 증가시킴

 

위의 과정을 치즈인 부분이 0이 될때까지 (cnt == 0) 반복하고, cnt가 0이되면 횟수를 출력해주면 답을 구할 수 있음. 참고로 answer이 -1부터 시작인 이유는 문제에서 별도로 '1'이 최소 하나 이상 있다고 제시하지 않았으므로, 맨 처음부터 모두 0일 수 있기 때문임(이 경우 0을 출력)

 

 

예를들어 다음과 같은 입력이 주어졌다고 보자. (구현 방식은 매우 많음. 이하 예시는 제 코드 기준의 설명임)

 

그럼 좌측상단(0,0)부터 dfs를 진행해서 탐색을 한다면 안쪽에 들어있는 0으론 탐색이 진행되지 않으므로 (dfs시 탐색될 곳을 파란색 글자로 표현함) 문제에 제시된 조건을 만족시킬 수 있음.

 

제가 짠 코드 기준으로 보자면 파란색 부분의 dfs 진행 후 배열의 모습은(42 line이 끝난 후) 아래와 같이 나오게 된다.

 

45~50 line을 통해 2면 이상 닿은 빨간부분은 0이 되고(공기로 변경), 2였던 부분은 다시 1로 초기화 함.

그렇게 모두 0이 될 때 까지 반복하게 되는데, 그림의 예시에서는 다음에 모두 제거되니 한 번 더 진행하면 모두 사라짐!

 

 

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2638.java