(C++) - 백준(BOJ) 17070 : 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

모든 경우를 backtracking으로 탐색해 해결한 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. 집 한변의 길이 n, 집의 구조를 입력받을 2차원 배열 house, n행 n열에 도착하는 경우의 수를 출력할 cnt를 선언합니다.

 2. 길이 n행 또는 n열을 초과하는 모두 벽으로 생각해 house의 값들을 모두 1로 초기화해줍니다.

 3. 1행 1열 ~ n행 n열까지 house에 nXn만큼 입력해줍니다.

 

📔 풀이과정

항상 우측방면으로 밖에 갈 수 없기 때문에 경우의 수가 매우 적어집니다. 100만 안으로 input이 주어지기 때문에 모든 경우의 수를 확인하는 방식을 다양하게 구현해서 ac를 받을 수 있습니다. 또한 이동방향의 제한으로 인해 바파이프의 뒤쪽은 고려할 필요가 없습니다.

 

backtracking함수를 시행합니다.

기저 case는 벽을 만났다면 종료, n행 n열에 도착했다면 cnt++ 후 함수를 종료해줍니다.

 1. 이전 파이프 방향이 가로방향(dir = 1)이면 가로 또는 대각선으로 밖에 갈 수 없습니다.

 2. 이전 파이프 방향이 세로(dir = 2)면 세로 또는 대각선으로만 갈 수 있습니다.

 3. 이전 파이프 방향이 대각인 경우 빈칸을 확인해 (r행 c+1열), (r+1행 c열), (r+1행 c+1열)이라면 대각으로 갈 수 있으므로 다름 재귀함수를 호출해줍니다.

 

1 ~ 3 경우 모두 대각으로 갈 수 있으므로 이는 하나로 묶어주어 재귀를 수행합니다. 

📔 정답출력

cnt를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int house[20][20], n, cnt;
void backtracking(int r, int c, int dir){
    if(house[r][c]) return;
    if(r == n && c == n) { cnt++; return; }
    if(dir == 1) backtracking(r, c + 1, 1);
    if(dir == 2) backtracking(r + 1, c, 2);
    if(dir == 3) backtracking(r, c + 1, 1), backtracking(r + 1, c, 2);
    if(!house[r][c+1] && !house[r+1][c] && !house[r+1][c+1])
        backtracking(r + 1, c + 1, 3);
}
int main(){
    memset(house, 1, sizeof(house));
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) 
            cin >> house[i][j];
    
    backtracking(1,2,1);
    cout << cnt;
}