티스토리 뷰
풀이
이 문제는 백트래킹을 이용하여 해결할 수 있는 문제다. 파이프를 생성하고 그 경로는 다시는 사용되서는 안되므로 DFS를 사용하여야 한다. 생성되어야 할 파이프의 개수는 최대로 출력되어야한다. 이 말은 파이프는 빵집의 제일 위부터 연결되면(우상, 우, 우하 중에서 우상을 우선) 최대로 파이프를 만들 수 있다.
DFS탐색을 행의 개수만큼진행하면서 만약 파이프가 생성되면 그대로 전부 return을 해주면서 그 파이프를 다시는 사용할 수 없게 만든다.( 방문배열 v에서 방문했다고 true로 체크는 했지만 돌아오면서 false로 바꾸지 않는다)
코드
'알고리즘' 카테고리의 다른 글
| <baekjoon> 회전하는 큐 (0) | 2020.08.30 |
|---|---|
| <baekjoon> 말이 되고픈 원숭이 (0) | 2020.08.29 |
| <baekjoon> 벽 부수고 이동하기 (0) | 2020.08.26 |
| <baekjoon> 치킨 배달 (0) | 2020.08.25 |
| <baekjoon> 단어 수학 (0) | 2020.08.22 |