(JAVA) 백준 16197번 : 두 동전 --- [백트래킹]

www.acmicpc.net/problem/16197

16197번: 두 동전

 

안녕하세요.

 

이 문제는 백트래킹 알고리즘을 사용하여 해결했습니다.

 

 

특히,

 

버튼은 총 10회를 넘지 않는다는 조건과

네 방향으로 이동할 수 있다는 조건,

동전이 하나라도 밖으로 나가게 하는 최소 회수 를 찾아야 하는 것

 

을 통해 백트래킹을 사용한다는 것을 알았습니다.

 

 

BFS 알고리즘을 사용해도 되지만,

조건이 여러모로 까다롭고 방문 체크 파악하기도 어렵기 때문에 백트래킹 알고리즘을 사용했습니다.

 

 

그렇기 때문에, 이 문제는 상황에 맞는 조건들만 예외처리를 하면 됩니다.

 

 

  1)  버튼을 10회 이상 누르면 종료하는 조건

  

  2)  두 동전을 하나만 빠져나갔는지 체크하는 조건 (두 동전 둘 다 빠져나가면 PASS)

    ->  하나의 동전만 빠져나가는 것을 파악하는 순간, 백트래킹을 종료시키면서 Math.min을 통해 최소 카운팅 값을 얻습니다.

 

  3)  동전을 이동시키려는 위치가 벽인지 파악하는 조건 (벽이면 그 자리에 멈춰야하니까)

 

  4)  위 1,2,3 조건을 통과하면 버튼 누르는 횟수를 1 증가시키면서 백트래킹 진행(재귀 함수호출)

 

 

이렇게 나온 결과는 최솟값!

 

 

이상입니다.

 

감사합니다!

 

 

 

 

소스코드

---