[C] Backjoon 17070 파이프 옮기기1

백준 17070번 문제는 파이프 옮기기 1이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

문제 요구 사항을 분석하면 아래와 같다.

1. 3 방향에 대한 이동
2. 이전 이동 방향에 대한 정보 전달
3. 1 & 2 를 바탕으로 하는 조건부 이동
4. 최종 도달 목표(종료조건 = N * N)
5. 도달 경우의 수 계산을 위한 반복문 필요

문제 상세 요건 및 분석사항은 아래와 같다.

1. 행과 열의 인덱스를 1부터 시작한다.
2. 배열로 구현할 경우 매 순간에 배열의 범위를 벗어나면 안된다.
3. 대각 이동에서 우상단과 좌하단에 벽이 위치하면 안된다.
4. 처음 파이프 위치는 (1, 1)와 (1, 2) 이고 항상 빈칸이다.

#include <stdio.h>

int house[20][20];
int visit[20][20];
int dx[]={0,1,1};
int dy[]={1,0,1};
int count;

void DFS(int x, int y, int N, int prev){    
    if (x==N && y == N){
        // End condition with counting
        count++;
    }
    else{
        for (int i=0; i<3; i++){
            // 3 directional movements are implemented using for loop 
            int nx = x + dx[i];
            int ny = y + dy[i];
            // if statement for condition check 
            if (nx >N || ny>N || visit[nx][ny]==1|| house[nx][ny]==1 ) continue;
            if (prev==0 && i == 1) continue;
            else if (prev ==1 && i==0) continue;
            else if (i==2 && (house[nx-1][ny] == 1 || house[nx][ny-1] == 1)) continue;
            else {
                visit[nx][ny]=1; 
                DFS(nx,ny,N,i); 
                visit[nx][ny]=0; 
            }           
        }
    }
}


int main(){
    // input 
    int N;
    scanf("%d", &N);    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            scanf("%d", &house[i][j]);
        }
    }
    // DFS
    DFS(1, 2, N, 0);
    // Print out the result
    printf("%d", count);
    return 0;
}