[백준_BOJ] 3109. 빵집 문제풀이 JAVA

문제

 

 

 

 

 

 

풀이

 

 

먼저 dfs에서 이동 가능한 경로는 ↗ → ↘ 이므로 di 배열은 { -1 0 1 } 로 선언해주었습니다.

그 다음 항상 가장 왼쪽 열에서 출발하므로 for문을 통해 dfs( i , 0 ) 으로 동작시켜주었습니다.

 

          문제 풀이에서 가장 중요한 부분은 문제에 있는 힌트 그림인 것 같습니다.

 

파이프가 중복이 불가능하기 때문에 dfs로 이동을 하다가 만약 더이상 진행이 불가능하다면

( dfs 함수 속 for 문이 모두 종료된다면 )  해당 경로를 모두 false로 반환해주어야 합니다.

문제 풀이 시에 이 부분 때문에 한참 헤맸습니다.

 

앞으로 계속 진행이 가능한 경우 dfs( next_i, next_j ) 를 통해 next_j 가 M - 1에 도달할 때까지

진행 시켜주고 오른쪽 끝 열에 도착할 경우 cnt를 증가시켜 답을 찾아주었습니다.

 

 

 

 

코드

 

 

 

 

 

출처

 

 

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

3109번: 빵집