알고리즘 코딩기법 - 8. 쉬어가기

안녕하세요. 17-2기 조일룡입니다.

기말고사 시험기간인데 다들 공부 잘 하고 계신지 모르겠네요.
저는 이번 기말고사 션하게 말아먹을 것 같습니다. ㅠ

기말고사 시즌인 관계로 이번 블로그는 머리를 식힐겸 퍼즐을 하나 준비했습니다.

이건 18-2기 여러분들 들어오셨을 때 집중세미나 시간에 했던거 재탕인데요.. 뭐 뒷북이지만 괜찮겠지여 ㅋㅋ


지뢰찾기 퍼즐

지뢰찾기는 다 해보셨으리라 생각되므로 자세한 설명은 생략하겠습니다.

위의 지뢰판에서 숫자는 자기과 양옆의 칸에 있는 지뢰의 수를 알려줍니다. 한 칸에는 최대 하나의 지뢰만이 있을 수 있습니다.

그렇다면 위의 그림에는 몇 개의 지뢰가 있을까요?


지뢰찾기 고수분들은 그림 대충 보고 지뢰가 어디에 있는지 금방 찾으실거라 생각되는데여 사실 지뢰찾기 한 번도 해보지 않은 사람이라도 이 문제의 해법은 상당이 간단합니다.

답부터 말하자면 지뢰의 수는 2 + 1 + 1 + 2 = 6 입니다.

위 그림을 보면 어째서 2 + 1 + 1+ 2 가 답인지 눈치를 채실 수 있으리라 생각합니다.

붉은 색으로 표시된 칸에 적힌 숫자는 그 칸을 포함하여 양옆까지 총 3개의 칸에 존재하는 지뢰의 수를 알려줍니다. 즉 연속한 3칸을 한 단위로 보면 그 중 가운데 칸이 그 한 단위에 있는 지리의 수를 알려주는겁니다. 그렇다면 우리는 단순히 지뢰밭을 3개를 한단위로 나누어 그 각 단위별로 지뢰수를 모두 더하면 전채 지뢰밭에 있는 지뢰 수를 알게 되는 거지요.

그런데 여기에는 문제가 있습니다. 바로 이 방법은 3의 배수일때만 가능하다는 겁니다. 아래의 경우를 봅시다.

위와 같이 3개를 한단위로 쪼개보겠습니다.

그림을 보면 처음 9개의 칸에는 모두 5개의 지뢰가 있는 것을 알 수 있지만 마지막 칸에 지뢰가 있는지 없는지 확신을 가질수가 없습니다. 결국 지뢰찾기를 다 해봐야 전체 지뢰의 갯수를 알 수가 있게 됩니다. 하지만 여기에 간단한 해결책이 있습니다.

어떤가요? 전체 지뢰 갯수가 1 + 1 + 2 + 1 = 5 라는 것을 한 눈에 알 수 있습니다.


이제 우리는 아래 지뢰판에 지뢰가 몇 개인지도 쉽게 알 수 있습니다.

10 * 10 크기의 지뢰판인데여.. 지뢰가 어디있는지 찾으려면 힘들지만 지뢰가 몇개인지 아는 것은 이제 문제가 안됩니다.

가로세로 모두 크기가 10 (3n+1의 형태) 이므로 양쪽끝 단위의 길이는 2, 가운데는 3이 되도록 나눈뒤 가운데 칸의 수만 다 더하면 됩니다.

총 지뢰수는 1 + 2 + 1 + 2 + 2 + 2 + 1 + 2 + 1 + 3 + 2 + 2 + 2 + 1 + 2 + 4 = 30 이네요..

아래의 지뢰 지도를 보면 지뢰가 30개 맞다는 것을 알 수 있습니다.
(처음 지뢰판을 보고 정답표를 맞추기는 쉽지 않을것 같습니다;;)

오늘 포스팅은 여기서 마치겠습니다.

당장 보기에 어려워 보이는 문제라도 살짝 다른 시각에서 보면 간단한 해법이 존재할 수 있다는 것을 생각하시기 바랍니다.