[백준]17070 파이프 옮기기 1, C++

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

문제 요약

두칸짜리 파이프를 옮겨 (N,N) 위치까지 옮기는 방법의 개수 구하기

파이프는 세가지 방향으로만 움직일수 있음

접근 및 알고리즘

1.

메모리 제한이 512MB인거보면 DP다.

세가지 방향으로 움직일수 있는지 확인 (checkMove)
Top Down 방식으로 해당 위치에 값이 있으면 값 리턴, 끝에 도착하면 1을 저장하고 리턴

전체 코드

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

#define MAX_N 16

typedef struct item {
    pair<int, int> front;
    pair<int, int> rear;
    int dir;
} ITEM;

int N, answer;
int map[MAX_N][MAX_N];
int visit[MAX_N][MAX_N][3];

unordered_map<int, pair<int,int>> direction {
    {0, {0, 1}}, // r
    {1, {1, 1}}, // dr
    {2, {1, 0}}, // d
};

void init()
{
    cin >> N;
    for (size_t i = 0; i < N; i++)
        for (size_t j = 0; j < N; j++)
            cin >> map[i][j];
}

int checkMove(ITEM item)
{
    int fr, fc, rr, rc;
    fr = item.front.first;
    fc = item.front.second;
    if (0 > fr || fr >= N || 0 > fc || fc >= N) return 0;

    rr = item.rear.first;
    rc = item.rear.second;

    switch(item.dir)
    {
        case 0: case 2:
        {
            if (map[fr][fc]) return 0;
        }
        case 1:
        {
            if (map[fr][fc] || map[fr][rc] || map[rr][fc]) 
                return 0;
        }
    }
    return 1;
}


ITEM makeNextItem(ITEM cur, int dir)
{
    return {
        {
            cur.front.first + direction[dir].first,
            cur.front.second + direction[dir].second
        },
        {
            cur.front.first,
            cur.front.second
        },
        dir,
    };
}

int dfs(ITEM cur)
{
    if (cur.front.first == N-1 && cur.front.second == N-1)
        return 1;

    if (visit[cur.front.first][cur.front.second][cur.dir])
        return visit[cur.front.first][cur.front.second][cur.dir];

    ITEM tmp;
    int ret = 0;
    switch(cur.dir)
    {
        case 0:
        {
            tmp = makeNextItem(cur, 0);
            if (checkMove(tmp)) ret += dfs(tmp);

            tmp = makeNextItem(cur, 1);
            if (checkMove(tmp)) ret += dfs(tmp);
        }
        break;
        case 1:
        {
            tmp = makeNextItem(cur, 0);
            if (checkMove(tmp)) ret += dfs(tmp);

            tmp = makeNextItem(cur, 1);
            if (checkMove(tmp)) ret += dfs(tmp);

            tmp = makeNextItem(cur, 2);
            if (checkMove(tmp)) ret += dfs(tmp);
        }
        break;
        case 2:
        {
            tmp = makeNextItem(cur, 1);
            if (checkMove(tmp)) ret += dfs(tmp);

            tmp = makeNextItem(cur, 2);
            if (checkMove(tmp)) ret += dfs(tmp);
        }
        break;
    }

    visit[cur.front.first][cur.front.second][cur.dir] = ret;
    return ret;
}

int main()
{
    init();
    cout << dfs({{0,1}, {0,0}, 0}) << endl;
    return 0;
}

전체코드 2

얘가 조금더 빠르다.

#include <iostream>
#include <queue>
using namespace std;

#define MAX_N 16

int N, answer;
int map[MAX_N][MAX_N];
int visit[MAX_N][MAX_N][3];

void init()
{
    cin >> N;
    for (size_t i = 0; i < N; i++)
        for (size_t j = 0; j < N; j++)
            cin >> map[i][j];  
}

int checkMove(int fr, int fc, int rr, int rc, int dir)
{
    if (0 > fr || fr >= N || 0 > fc || fc >= N) return 0;

    switch(dir)
    {
        case 0: case 2:
        {
            if (map[fr][fc]) return 0;
        }
        case 1:
        {
            if (map[fr][fc] || map[fr][rc] || map[rr][fc])
                return 0;
        }
    }
    return 1;
}


int dfs(int fr, int fc, int rr, int rc, int dir)
{
    if (fr == N-1 && fc == N-1)
        return 1;

    if (visit[fr][fc][dir])
        return visit[fr][fc][dir];

    int ret = 0;
    switch(dir)
    {
        case 0:
        {
            if (checkMove(fr, fc + 1, fr, fc, 0))
            ret += dfs(fr, fc + 1, fr, fc, 0);

            if (checkMove(fr + 1, fc + 1, fr, fc, 1))
            ret += dfs(fr + 1, fc + 1, fr, fc, 1);
        }
        break;

        case 1:
        {
            if (checkMove(fr, fc + 1, fr, fc, 0))
            ret += dfs(fr, fc + 1, fr, fc, 0);

            if (checkMove(fr + 1, fc + 1, fr, fc, 1))
            ret += dfs(fr + 1, fc + 1, fr, fc, 1);

            if (checkMove(fr + 1, fc, fr, fc, 2))
            ret += dfs(fr + 1, fc, fr, fc, 2);
        }
        break;

        case 2:
        {
            if (checkMove(fr + 1, fc + 1, fr, fc, 1))
            ret += dfs(fr + 1, fc + 1, fr, fc, 1);

            if (checkMove(fr + 1, fc, fr, fc, 2))
            ret += dfs(fr + 1, fc, fr, fc, 2);
        }
        break;
    }

    visit[fr][fc][dir] = ret;
    return ret;
}

int main()
{
    init();
    cout << dfs(0, 1, 0, 0, 0) << endl;
    return 0;
}