<baekjoon> 빵집

풀이

이 문제는 백트래킹을 이용하여 해결할 수 있는 문제다. 파이프를 생성하고 그 경로는 다시는 사용되서는 안되므로 DFS를 사용하여야 한다. 생성되어야 할 파이프의 개수는 최대로 출력되어야한다. 이 말은 파이프는 빵집의 제일 위부터 연결되면(우상, 우, 우하 중에서 우상을 우선) 최대로 파이프를 만들 수 있다. 

DFS탐색을 행의 개수만큼진행하면서  만약 파이프가 생성되면 그대로 전부 return을 해주면서 그 파이프를 다시는 사용할 수 없게 만든다.( 방문배열 v에서 방문했다고 true로 체크는 했지만 돌아오면서 false로 바꾸지 않는다)

 

코드