[BOJ] 백준 2636번 : 치즈 (JAVA)

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

 

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

 

 

 

 

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

 

 

 

 

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

 

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

 

 

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

 

풀이

DFS를 이용하여 풀 수 있는 문제였습니다.

 

외부 공기와 맞닿은 치즈가 녹는데, 몇 초만에 모든 치즈가 녹을 것이고, 다 녹기 1초 전에는 몇 개의 치즈가 있었는지 구하는 것이 핵심이었습니다.

 

저는 처음에 치즈를 기준으로 상하좌우 방향에 공기가 있는지 확인하고, 공기가 있으면 지우면 방식으로 로직을 짜려고 했으나, 치즈 안에 공기가 있을 때는 치즈가 녹지 않는 반례가 있었습니다.

 

 

그래서 치즈가 아닌, 공기를 기준으로 상하좌우 방향을 DFS로 탐색하면서 외부 공기와 맞닿은 치즈를 찾아야 합니다.

문제에서 판의 테두리에는 치즈가 위치할 수 없다는 조건을 주었기때문에 (0, 0)은 반드시 공기입니다.

 

 

그리고 주의할 점이 한 가지 더 있습니다.

(0, 0)에서 시작해서 외부 공기와 맞닿은 치즈를 찾았을 때, 바로 map[i][j] = 0 과 같이 그 치즈를 즉시 공기로 만들어 버리면 안 됩니다.

 

 

만약, 특정 판이 "011" 인 구간이 있다고 가정하면, 왼쪽에서 2번째에 있는 1은 공기와 맞닿아 있는 것은 자명합니다.

하지만, 이 1을 바로 0으로 만들어버리면 동시에 오른쪽에서 1번째에 있는 1도 외부 공기와 맞닿아 있다고 판단해 버리게 됩니다.

 

따라서 바로 map[i][j] = 0 으로 처리하는 것이 아니라, 임의의 숫자를 주어서 "1초 뒤 녹을 예정인 치즈"라는 의미를 담아야 합니다. 저는 2 라는 숫자를 주기로 하였습니다.

 

 

이제, DFS를 돌리면서 마지막 점까지 탐색이 끝났다고 합시다.

마지막 점까지 탐색이 끝났다는 의미는 1초가 지났다는 뜻이기때문에 "1초 뒤 녹을 예정인 치즈"를 모두 녹여줘야 합니다.

 

여기서, 저는 isCheese() 라는 반환형이 boolean인 메소드를 하나 정의하였습니다.

이 메소드는 "1초 뒤 녹을 예정인 치즈"를 모두 녹여주고, 맵 전체에 치즈가 하나라도 남아있는지 확인하는 메소드입니다.

 

 

이 메소드의 반환값은 true 또는 false이기때문에 메인 메소드의 반복문의 조건으로 지정하면, 몇 초뒤에 치즈가 모두 녹는지 판단하기 용이합니다.

 

자세한 소스코드는 아래를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.