[Python] 음료수 얼려 먹기 문제

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

 

다음은 예시이다.

 

입력

4 5

00110

00011

11111

00000

 

 

출력 

3

----------------------------------------------------------------------------------------------------------------------------

<해설>

 

입력 처음에는 N x M크기가 주어지고 다음은 틀이 주어진다.

 

예시는

 

0 0 1  1  0

0 0 0 1  1

1  1  1  1  1

0 0 0 0 0

 

이런 얼음칸이 주어졌던 것이고 여기서 크게 3개의 조각이 만들어지므로 출력이 3이 된 것이다.

어떻게 하면 알고리즘화 시킬 수 있을까? 

이 문제는 1칸씩 돌아가면서 DFS로 풀어야 하는 문제이다.(재귀함수를 사용한다고 생각하면 쉽다.)

선택된 칸의 사방으로 확장할 수 있으면 확장해서 다시하면 재귀를 돌리면 결국 확장가능한 곳까지 뻗어나간다.

그러므로 다음과 같은 코드로 쉽게 만들 수 있다.

여기서 주의할 점은 갈 수 있는 방향이 없을 때 아무것도 하지 않아도 된다는 것이다. 또한 확장을 해야하는 것이기 때문에 함수를 만약

 

1. 현재 방향에서 갈 수 있나요?

2-1. 갈 수 있으면 가세요.   2-2)  못가면 오른쪽 90도 회전하세요(만약 다 못가면 종료)

3. 재귀

 

를 계속 돌리면 될 것 같지만 이러면 커버가 안되는 공간이 생긴다.. (깊게 생각해보기 바란다. 예시로도 알 수 있다.)

 

위의 생각은 최단경로에서 더 어울리는 생각일 수 있다.(단 최단경로 방향을 생각하고 회전을 고려해야한다.)

또한 최단경로는 많은 경우에 따라 BFS가 더 좋을 수 있다.

 

따라서 문제를 보고 어떻게 풀지 초반에 잘 다듬는 연습을 하자.