[백준][완전탐색] 17070 파이프 옮기기 c++구현

목차

https://www.acmicpc.net/problem/17070

문제

 

문제 구현 방향 

처음에는 dp로 시도했다가 문제를 풀다보니 완전탐색으로 방향성이 바뀌어 버렸다..

파이프 옮기기2가 있다는데 그거는 dp로 풀어보아야 겠다.

각 끝점에서 이동할 수 있는 좌표를 저장해주고 그거 대로 탐색한 뒤에 원복해서 백트래킹을 해주었다.

 

 

문제 구현 시 주의점

완전 탐색으로 하면 시간을 더 줄여야 맞을 수 있다. 그래서 나는 좌표가 끝점에 도달했을 때 특정 방향이면

재귀가 종료하게끔 더 추가하였다. 

 

 

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;

//pipe 구조체
typedef struct Pipe {
    int x; 
    int y;
    int d;
}Pipe;

int board[17][17] = { 0 };

int total = 0;
int N;
void nextNode(int x, int y, int d, vector<Pipe>&v) {
    if (d == 0) {
        int nx = x + 1;
        int ny = y;
        v.push_back({ nx, ny, 0 });
        nx = x + 1;
        ny = y + 1;
        v.push_back({ nx, ny, 1 });
    }
    else if (d == 1) {
        int nx = x + 1;
        int ny = y;
        v.push_back({ nx, ny, 0 });
        nx = x + 1;
        ny = y + 1;
        v.push_back({ nx, ny, 1 });
        nx = x;
        ny = y + 1;
        v.push_back({ nx, ny, 2 });
    }
    else if (d == 2) {
        int nx = x + 1;
        int ny = y + 1;
        v.push_back({ nx, ny, 1 });
        nx = x;
        ny = y + 1;
        v.push_back({ nx, ny,2 });
    }
}

void dfs(int curx, int cury, int curd, int caculating[17][17]) {
    if (curx == N - 1 && cury == N - 1) {
        total += caculating[N - 1][N - 1];
        return;
    }
    if (curx == N - 1 && curd == 0) {
        return;
    }
    if (cury == N - 1 && curd == 2) {
        return;
    }

    vector<Pipe> v;
    nextNode(curx, cury, curd, v);
    for (Pipe p : v) {
        if (p.d == 0) {
            if (board[p.y][p.x] || p.y > N - 1 || p.y< 0 || p.x > N - 1 || p.x < 0)
                continue;
            int save = caculating[p.y][p.x];
            caculating[p.y][p.x] += caculating[cury][curx];
            dfs(p.x, p.y, p.d, caculating);
            caculating[p.y][p.x] = save;
        }
        else if (p.d == 1) {
            if (board[p.y][p.x] || p.y > N - 1 || p.y< 0 || p.x > N - 1 || p.x < 0)
                continue;
            int cx = p.x - 1;
            int cy = p.y;
            if (cx >= 0 && cx <= N - 1 && cy >= 0 && cy <= N - 1) {
                if (board[cy][cx])
                    continue;
            }
            cx = p.x;
            cy = p.y-1;
            if (cx >= 0 && cx <= N - 1 && cy >= 0 && cy <= N - 1) {
                if (board[cy][cx])
                    continue;
            }
            int save = caculating[p.y][p.x];
            caculating[p.y][p.x] += caculating[cury][curx];
            dfs(p.x, p.y, p.d, caculating);
            caculating[p.y][p.x] = save;
        }
        else if (p.d == 2) {
            if (board[p.y][p.x] || p.y > N - 1 || p.y< 0 || p.x > N - 1 || p.x < 0)
                continue;
            int save = caculating[p.y][p.x];
            caculating[p.y][p.x] += caculating[cury][curx];
            dfs(p.x, p.y, p.d, caculating);
            caculating[p.y][p.x] = save;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int caculating[17][17] = { 0 };
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    caculating[0][1] = 1;
    dfs(1, 0, 0, caculating);
    cout << total;
    return 0;
}