BOJ#3109 빵집 (PLINOVOD)

BOJ#3109 빵집 (PLINOVOD)

* 문제

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

* 풀이

<조건>

1) 가스관과 빵집을 연결하는 가스 파이프 라인은 첫번째 열에서 시작하고, 마지막 열에서 끝나게 됩니다. 

2) 첫번째 열과 마지막 열은 항상 비어있습니다.

3) 각 칸은 3가지 방향으로 (↗️, ➡️, ↘️) 연결할 수 있습니다.

4) 건물이 있을 경우 파이프를 설치할 수 없고, 파이프끼리 겹칠 수도 없습니다.

<구현>

1번 조건

 : 첫번째 열에서 시작하여 마지막 열까지 진행 후 return 되는 Backtracking 함수 구현

 : 마지막 열 도달 시 1을 return하여 파이프라인 개수를 증가시킨다.

2번, 3번 조건

 : 첫번째 열은 모든 행을 검사해야 하고, 그 다음부터는 최대 3개의 행만 검사

 : 한 셀에서 이어지는 3개의 경로 중 하나라도 마지막 열에 도달 시, 나머지 경로 검사는 불필요 하므로 검사하지 않는다.

4번 조건

 : 2차원 행렬을 이용하여 map 정보를 입력받고, 설치 가능 지역을 0으로 표시. 건물과 이전에 설치된 파이프는 0값이 아닌 다른 값을 가지도록 한다.

 : 파이프를 설치할 때마다 map정보를 업데이트한다.

 : 업데이트한 map 정보는 되돌리지 않는다.

(파이프 라인을 놓을 수 있는 모든 경우의 수를 구하는 것이 아니라, 놓을 수 있는 파이프 라인의 최대 개수를 구하는 것)

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%233109_PLINOVOD/src