백준 2251. 물통

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

2251번: 물통

 

dfs로 풀기로하고 고민한 것은 재귀를 어느 시점에 리턴할것인가이다.

물을 붓는것을 물통으로 이동하는것처럼 표현하면 

A에서는 B,C 로

B에서는 A,C로 

C에서는 A,B로 이동이 가능하다.

 

이렇게 dfs를 돌리면 이동가능한 모든 순열이 나올것인데 

A B C 는 모두 서로에게 이동 가능하기 때문에 끝이 없다.

그러면 이동하면서 이미 탐색한 것을 기록을 해놔야하는데 어떤식으로 기록할지가 문제였다.

해결한 방법은 3차원 배열을 만들어서 해결했다.

물통이 총 3개 이므로 3차원 배열을 만들어 각 차원에 해당하는 물통의 물의 양을 저장하고 

이미 해당 하는 물들의 양으로 방문한적이 있다면 이동하지 않는다.

 

예를들어 mark[2][3][10]은 

A에 2리터, B에 3리터, C에 10리터 인 상황은 이미 방문했다는 뜻이다.