[백준] 17070.cpp : 파이프 옮기기 1

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

---

• 파이프는 오른쪽 - 아래쪽 까지 90도 밖에 회전할 수 없기 때문에, 왼쪽 파이프가 끝점에 도달할 일은 없다.
• 파이프를 한번 이동시킬 때, 오른쪽 파이프가 반드시 다음 위치의 왼쪽 파이프가 되기 때문에 왼쪽 파이프에 대한 검사는 할 필요 없다.
• 따라서 점 하나만을 특정 조건에 맞게 (N, N) 까지 도달시키면 된다.
• 이전에 움직였던 방향이 주어지면 점이 다음에 갈 수 있는 방향이 고정적으로 주어졌기 때문에, 모든 방향에 대해서 재귀 호출 하면 된다.
• 인덱스와 벽에 대한 검사만 매번 해준다.

---

#include <iostream>

using namespace std;

int n, temp;
int map[17][17];
int answer;

void dfs(int row, int col, int state)       // 왼쪽 파이프는 항상 유효하기 때문에 고려할 필요 없음, 오른쪽 파이프의 위치만 고려
{
    if(map[row][col] == 1) return;          // 만약 다음 위치가 벽이면 종료
    if(row > n || col > n) return;          // 인덱스 초과 시 종료
    if(state == 3)                          // 대각선으로 내려왔을 경우는 위쪽과 왼쪽도 벽일 경우 종료
        if(map[row-1][col] == 1 || map[row][col-1] == 1) return;

    if((row == n && col == n))              // 만약 끝점에 도달했을 경우는
    {                                       // 경로 카운트 증가시키고 종료
        answer++;
        return;
    }
    
    if(state == 1)                          // 가로로 왔을 땐
    {
        dfs(row, col + 1, state);           // 두 가지 방법으로 일단 보내봄 (유효성 검사는 앞에서 하므로)
        dfs(row + 1, col + 1, 3);
    }
    else if(state == 2)                     // 세로
    {
        dfs(row + 1, col, state);
        dfs(row + 1, col + 1, 3);
    }
    else                                    // 대각선
    {
        dfs(row, col + 1, 1);
        dfs(row + 1, col, 2);
        dfs(row + 1, col + 1, 3);
    }
}

int main()
{
    cin >> n;
    for(int r = 1 ; r <= n ; r++)
        for(int c = 1 ; c <= n ; c++)
            cin >> map[r][c];
                                            // 처음에 (1,1) (1,2) 에서 시작하게 될 경우에는
    dfs(1, 3, 1);                           // 가로로 보내고
    dfs(2, 3, 3);                           // 대각선으로 보낼 수 있다

    cout << answer << endl;
}

---

 

---

• 2등 소스코드 참고 : www.acmicpc.net/source/17159943
• 3차원 DP 배열을 사용하여, 가로 세로 대각선 3개에 대해 각각 2차원 배열을 만들었다.
• 반복문 내에서, 각 상태별로 유효성을 검사하며 이전 DP 값을 더해나가는 식이다.

---

#include <cstdio>

int n, map[17][17];
int dp[3][17][17];

int main()
{
    scanf("%d", &n);
    for(int r = 1 ; r <= n ; r++)
        for(int c = 1 ; c <= n ; c++)
            scanf("%d", &map[r][c]);

    dp[0][1][2] = 1;
    for(int r = 1 ; r <= n ; r++)
    {
        for(int c = 1 ; c <= n ; c++)
        {
            if(map[r][c] == 1) continue;
            for(int i = 0 ; i < 2 ; i++) dp[0][r][c] += dp[i][r][c-1];
            for(int i = 1 ; i < 3 ; i++) dp[2][r][c] += dp[i][r-1][c];
            for(int i = 0 ; i < 3 ; i++) if(!map[r-1][c] && !map[r][c-1]) dp[1][r][c] += dp[i][r-1][c-1];
        }
    }
    
    printf("%d\n", dp[0][n][n] + dp[1][n][n] + dp[2][n][n]);
}