[BOJ 17069 // C++] 파이프 옮기기 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17069번 문제인 파이프 옮기기 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

이 문제는 DP를 이용하여 해결할 수 있다. 각 집에 대응되는 칸에 그 점까지 들어오는 가로방향 파이프의 수, 세로방향 파이프의 수, 대각선방향 파이프의 수를 하나하나 기록해나가는 것이다. 기록이 끝나면 N행N열에 적힌 세 방향의 파이프의 개수의 합을 출력한다.

 

자세하게 쓰면 다음과 같다.

 

0) 각 집의 정보(빈 칸, 벽), 각 칸까지의 가로, 세로, 대각선으로 끝난 파이프 개수의 정보를 담을 배열을 만든다.

글쓴이는 각 i행j열의 성분에 크기 4의 배열을 주어 각 성분에 위의 내용을 담았다.

 

1) (1,2) 지점에 가로방향으로 끝나는 파이프가 하나 있다는 초기값을 입력한다.

 

2) 각 (i,j) 지점에서 윗 행에서 아래 행 방향으로, 같은 행 안에서는 왼쪽 열에서 오른쪽 열 방향으로 다음을 계산한다.

 

2-0) (i,j) 지점에 벽이 있다면 이 지점에 대한 조사를 건너뛴다.

2-1) (i,j) 지점에서 가로방향으로 끝날 수 있는 경우의 수를 기록한다.

이는 (i,j-1) 지점에서 가로방향으로 끝난 파이프 수와 대각선방향으로 끝난 파이프 수의 합과 같다.

2-2) (i,j) 지점에서 세로방향으로 끝날 수 있는 경우의 수를 기록한다.

이는 (i-1,j) 지점에서 세로방향으로 끝난 파이프 수와 대각선방향으로 끝난 파이프 수의 합과 같다.

2-3) (i,j) 지점에서 대각선방향으로 끝날 수 있는 경우의 수를 기록한다.

이는 (i-1,j-1) 지점에서 가로, 세로방향으로 끝난 파이프 수와 대각선방향으로 끝난 파이프 수의 합과 같다.

만약 (i,j-1) 지점이나 (i-1,j) 지점에 벽이 있다면 이 과정을 생략한다.

 

3) (N,N) 지점에서 가로, 세로, 대각선 방향으로 끝난 파이프 수의 합을 구해 출력한다. 답이 int 범위를 넘어서는 경우가 있으니 long long을 이용하자.

 

2-1과 2-2에서, 각 방향의 점이 벽인지 검사를 하지 않은 이유는 그 칸이 벽이라면 자연스럽게 0으로 채워지기 때문이다.

첫 행의 경우 그 위에 0으로 찬 행을 하나 만들면 위 알고리즘이 오류 없이 돌아갈 것이라는 것을 확인할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
typedef long long ll;

ll house[33][33][4]; // house[][][0] : 원래 집, 1 2 3 : 그 점으로 끝나는 가로/세로/대각선 파이프 수

int main()
{
    int N; cin >> N;
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            ll x; cin >> x;
            house[i][j][0] = x;
        }
    }
    house[1][2][1] = 1;
    for (int i = 1;i <= N;i++) {
        for (int j = 2;j <= N;j++) {
            if (i == 1 and j == 2) continue;
            if (house[i][j][0] == 1) continue;
            house[i][j][1] += house[i][j - 1][1] + house[i][j - 1][3];
            house[i][j][2] += house[i - 1][j][2] + house[i - 1][j][3];
            if (!(house[i - 1][j][0] == 1) and !(house[i][j - 1][0] == 1)) {
                house[i][j][3] += house[i - 1][j - 1][1] + house[i - 1][j - 1][2] + house[i - 1][j - 1][3];
            }
        }
    }
    cout << house[N][N][1] + house[N][N][2] + house[N][N][3];

    return 0;
}