SW Expert Academy 1868. 파핑파핑 지뢰찾기 (D4)

1868. 파핑파핑 지뢰찾기

이 문제는 N*N 크기의 지뢰 찾기 게임이 주어지고 지뢰의 위치를 사용자가 안다면, 최소 몇 번의 클릭을 통해 지뢰를 제외한 모든 지역에 숫자를 표시할 수 있는지 출력하는 문제입니다.

 

이번 문제는 지뢰찾기 룰에 대해 조금 알고 문제풀이에 들어가는 것이 좋습니다.

(이번 문제는 사용자가 지뢰의 위치를 알고 있기 때문에 지뢰를 클릭했을 때의 상황은 넘어가도록 하겠습니다.)

표의 각 칸을 클릭했을 때, 그 칸의 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 8칸에 대해 몇 개의 지뢰가 있는지 0에서 8 사이의 숫자로 클릭한 칸에 표시가 됩니다.

만약, 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정이기 때문에 해당 8방향의 칸도 자동으로 숫자를 표시해줍니다.

즉, 클릭한 칸의 숫자가 0일 경우 테두리가 0이 아닌 숫자가 나타날 때까지 모두 표시해준다는 뜻입니다.

그림 1

그림 1을 보시면 왼쪽의 C가 표시된 칸을 클릭한 경우 해당 칸의 숫자는 0이므로 0을 제외한 숫자들이 테두리를 감싸줄 때까지 확장을 하는 것을 확인할 수 있습니다. 

-> 0을 클릭할 경우 다른 칸까지 확장하여 숫자를 표시해주기 때문에 0을 통해 확장이 가능한 칸은 따로 클릭하기 보다는 0인 칸을 클릭해서 모두 숫자로 표시될 수 있도록 해주는 것이 클릭 수를 줄일 수 있는 방법이 될 것입니다.

 

위에서 알아낸 것을 통해 클릭을 먼저할 순서를 정해보겠습니다.

우선, 0인 칸을 클릭하여 해당 칸이 확장하면서 숫자인 칸들을 모두 보여줄 수 있도록 합니다.

모든 0인 칸을 클릭하면 남은 것은 확장이 불가능한, 8방향에 지뢰가 존재하는 칸들 뿐입니다. 해당 칸들은 각 칸마다 한 번의 클릭을 무조건해줘야 하므로 남은 칸의 개수만큼의 클릭 개수가 필요합니다.

 

i,j를 0~N-1을 순회하면서, queue에 좌표를 넣어주고 해당 칸의 8방향의 칸에 지뢰가 존재하는지 확인합니다. 존재하지 않다면 해당 칸의 8방향의 칸을 모두 queue에 넣어줍니다.

해당 8방향의 칸도 똑같이 진행해줌으로써 queue에 원소가 남지 않을 때까지 진행해주면, 0인 칸을 통해 확장할 수 있는 모든 칸을 숫자로 표시할 수 있게 됩니다. 해당 영역은 0인 칸 한 번의 클릭을 통해 숫자로 표시할 수 있는 칸들이 됩니다.

 

이번엔 정답을 구하는 방법을 작성해보도록 하겠습니다.

첫 answer=N*N으로 모든 칸을 클릭할 경우를 생각했습니다. 이 후 지뢰의 개수를 answer에서 빼주었습니다.

이 후, 0인 칸 주위를 확장하면서 숫자를 칸에 작성해줄 때, 확장에 의해 숫자가 적히게 되는 칸의 개수만큼 answer에서 빼주었습니다.

(확장에 의해 숫자가 자동으로 작성되는 칸은 클릭을 할 필요가 없어지는 칸이므로 확장 개수에서 빼줍니다.)

 

위의 과정을 모든 칸에 대해 수행이 완료될 경우 남은 횟수는 (0인 칸을 클릭한 횟수 + 8방향에 지뢰가 존재하는 칸 중 확장되지 않은 칸의 개수) 입니다.

 

 

 

이번 문제는 queue를 통해 특정 칸 주변 8방향으로 확장을 해 나갈 수 있는지 확인하는 로직을 세우는 것이 관건이었던 것 같습니다. 저와 같은 경우 거의 2중 for문을 통해 flag 변수로 해당 칸이 아직 확장되지 않은 칸인지 확인하는 방법을 통해 해당 문제를 해결했던 것 같습니다. Java의 queue 라이브러리 활용을 연습해볼 수 있는 좋은 기회였습니다.