backtracking
-
[백준 3109 - JAVA] 빵집Algorithm 2020. 11. 26. 11:40
3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 스터디 과제로 나왔지만, 예전에 풀었던 문제라서 코드를 보면서 복기만 해봤다. dfs를 이용했고, 모든 시작점에서 출발하여 파이프를 연결할 수 있을 경우 계속 진행하는 백트래킹 방식으로 풀었다. 풀이 방법 행의 수 만큼 dfs를 시작한다. 오른쪽위, 오른쪽, 오른쪽 아래로 이동하며 범위안이며 건물이 아닐 경우에만 dfs를 진행한다. 열의 끝에 도달한 경우 ans를 증가시킨다. import java.io.*; import java.util.*; public class Main {..