✅ DFS

문제

1. 해결 로직

모든 좌표에서 파이프가 가로, 세로, 대각선 중 어떤 모습으로 놓여져 있는지에 따라 이동 가능한 방향이 가로 - 2, 세로 - 2, 대각선 - 3 가지가 있다.
따라서 재귀적으로 이동시킨다. DFS

중복 연산을 막기 위해 이전 파이프가 놓여 있는 모양을 메모이제이션을 통해 저장해가며 진행을 해야할 것 같지만
문제에서 방법의 수는 항상 1,000,000보다 작거나 같다고 했으므로 중복 연산이 되더라도 시간초과가 되지 않는다는 것을 알 수 있다.
그냥 완전탐색으로 풀어도 된다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N, ans;
int map[17][17];

void DFS(int y, int x, int dir){ // dir : 가로(0), 세로(1), 대각선(2)
    if(y == N && x == N){
        ans ++;
        return;
    }

    if(dir == 0){ // 가로일 때
        // 가로로 보내기
        if(map[y][x+1] == 0 && x+1<=N) DFS(y, x+1, 0);
        // 대각선으로 보내기
        if(map[y][x+1] == 0 && map[y+1][x+1] == 0 && map[y+1][x] == 0 && x+1<=N && y+1<=N) DFS(y+1, x+1, 2);
    }
    if(dir == 1){ // 세로일 때
        // 세로로 보내기
        if(map[y+1][x] == 0 && y+1<=N) DFS(y+1, x, 1);
        // 대각선으로 보내기
        if(map[y][x+1] == 0 && map[y+1][x+1] == 0 && map[y+1][x] == 0 && x+1<=N && y+1<=N) DFS(y+1, x+1, 2);
    }
    if(dir == 2){ // 대각선일 때
        // 가로로 보내기
        if(map[y][x+1] == 0 && x+1<=N) DFS(y, x+1, 0);
        // 세로로 보내기
        if(map[y+1][x] == 0 && y+1<=N) DFS(y+1, x, 1);
        // 대각선으로 보내기
        if(map[y][x+1] == 0 && map[y+1][x+1] == 0 && map[y+1][x] == 0 && x+1<=N && y+1<=N) DFS(y+1, x+1, 2);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    DFS(1,2,0); // 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로

    cout << ans << "\n";

    return 0;
}

3. 시간 복잡도

O(3^N)

4. Review

DFS를 떠올리는게 중요했던 문제