[백준 17070번] 파이프 옮기기 (C++)

문제링크 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result = 0;
int arr[20][20];
int dx[] = {1, 0, 1};
int dy[] = {0, 1, 1};

void dfs(int y, int x, int z) // z=0 : 가로, 1 : 세로, 2 : 대각선
{
    if(x == N && y==N) //목표 지점 도착
    {
        result++;
        return;
    }

    for(int i=0; i<3; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if((z==0 && i==1) || (z==1 && i==0)) continue; //가로 -> 세로, 세로 -> 가로 불가능
        if(nx < 1 || nx > N || ny < 1 || ny > N ) continue; //범위 조건
        if(arr[ny][nx]) continue; //다음이 벽이면 불가능
        if(i==2 && (arr[ny][x] || arr[y][nx])) continue; //현재 대각선 일때, 추가로 옆 아래 확인
        dfs(ny, nx, i);
    }

}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
        }
    }

    dfs(1, 2, 0); //첫 위치

    cout << result;
    return 0;
}

bfs로도 풀 수 있고, dp로도 풀 수 있는 문제이다.

나는 bfs로 먼저 풀었다.

 

첫 위치인 (1, 2, 0) 을 시작으로 탐색을 시작한다.

여기서 z는 방향을 표시하며 0인 가로, 1은 세로, 2는 대각선을 표시한다.

 

우선 주어진 문제에서 이동 방법은 다음과 같다.

가로 -> 가로
가로 -> 대각선 3 방향
세로 -> 세로
세로 -> 대각선 3 방향 
대각선 -> 대각선 3방향

대각선 3방향은 →, ↘, ↓

따라서 첫번째로 가로 -> 세로와 세로 -> 가로는 불가능하기에 이를 체크해줘야 한다.

2번째로 범위 체크다 다음 x또는 y좌표가 1보다 작거나 N보다 커지면 안되므로 이것도 체크해준다.

3번째로이동했을 때 다음 위치에 벽이 있으면 안된다. 따라서 다음 좌표의 값이 1이면 불가능하다.

 

마지막으로 대각선 일때 추가적으로 확인해줘야 할 것이 생긴다.

기존 가로 세로 이동은 방향이 1가지 이기에 다음 좌표만 확인해줘도 되지만, 대각선의 경우 움직이는 방향이 3방향이므로 다음 좌표만 확인해주는 것이 아니라 추가적으로 2가지를 확인해줘야 한다.

그렇기에 현재 방향을 나타내는 i가 2일때 (대각선 일때) → 방향으로 꺾는 경우 벽이 있을 경우와, ↓ 방향으로 꺾는 경우 벽이 있을 경우를 확인해줘야 한다.

두 경우는 x나 y가 둘 중의 하나가 그대로인 상태에서 나머지 값이 이동하는 형태이므로 [ny][x] 나 [y][nx]의 값이 1인지를 체크해주면 된다.

 

이 모든 조건에 이상없을 경우 재귀함수를 계속 반복하여 목표 지점에 도착하는 경우를 카운팅한다.

 

아래는 dp로 푼 코드이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[20][20];
int dp[20][20][3]; //0 : 가로, 1 : 세로, 2 : 대각선

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[1][2][0] = 1; //초기위치
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
            if(i==1 && j<=2) continue;
            if(arr[i][j]==1) continue; //벽이면 불가능
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]; //가로 -> 가로 or 대각선 -> 가로
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]; //세로 -> 세로 or 대각선 -> 세로
            if(arr[i][j-1] || arr[i-1][j]) continue;
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]; //가로 -> 대각선 or 세로-> 대각선 or 대각선 -> 대각선
        }
    }

    cout << dp[N][N][0] + dp[N][N][1] + dp[N][N][2];
    return 0;
}

dp의 초기위치를 1로 초기화하고 시작한다.

그리고 dp배열의 마지막 [3]은 0 : 가로, 1 : 세로, 2 : 대각선이다.

 

수를 입력받으면서 바로 dp에 값을 저장하는데 초기값의 위치가 1, 2이므로 j의 값이 3보다 작을때는 스킵한다.

이후에 입력받는 값에 대해서 1일 경우에는 벽이어서 이동이 불가하므로 스킵한다.

 

벽이 아닐때는 이동이 가능하므로 이제 dp 배열을 갱신하는데

가로로 오는 경우, 세로로 오는 경우, 대각선으로 오는 경우 이렇게 3가지를 게산한다.

 

아래 각 경우에 대해서 살펴보면 다음과 같다.

<가로로 오는 경우>
가로 -> 가로
대각선 -> 가로

<세로로 오는 경우>
세로 -> 세로
대각선 -> 세로

<대각선으로 오는 경우>
가로 -> 대각선
세로 -> 대각선
대각선 -> 대각선

dp[i][j][0~2]는 dp[y][x][방향]이므로

가로 방향에 대해서 직전 가로에서 오는 경우 + 직전 대각선에서 오는 경우를 저장하고,

세로 방향에 대해서 직전 세로에서 오는 경우 + 직전 대각선에서 오는 경우를 저장하고,

대각선 방향에 대해서 직전 가로, 세로, 대각선에서 오는 경우를 저장해주면 된다.

대각선의 경우에는 가로, 세로 방향과 달리 추가적으로 직전 3방향에 대해서 모두 벽이 아닌지 체크가 필요하다.

 

이렇게 각 방향에 대해 오는 경우의 수를 저장하고 이 3가지 방향의 경우의 수를 전부 더해서 출력해주면 된다.