[백준] 17070 - 파이프 옮기기

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

위의 문제와 상당히 유사했고, 한번 유사문제를 풀어봤기 때문에 '음... 이런 느낌으로 풀면 되겠네?' 하고 슥슥 했는데 한번에 통과됨...

풀어놓고도 왜 된거지? 했음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

일단 이 문제는 dfs + dp의 유형이라고 본다.

한번 탐색했던 경로에 경로의 갯수를 저장, 즉, 끝까지 한번 가면 돌아오는길에 그 포인터에 이전에 갯수를 더해주고 저장한다.

최초에 목적지에 도착한 파이프는 그 지점에서 1개의 경로를 가지기 때문에 1을 return 받는다. 그럼 return 된 1이 이전의 좌표의 visit 배열에 더해주고 저장한다.

바로 이전 점에서 다른 경로를 탐색하고, return 받을 수 있다면 return 받은 값을 더하고 저장한다.

탐색할 곳이 없다면 dp에 저장된 값을 return하며 다른 경로를 탐색하기 위해 돌아간다.

이런 식으로 타고 돌아오다보면 최초 한번 경유했던 경로의 root의 길의 갯수가 저장이 된다. 

여기서 가지를 쳐주자면, 한번이라도 방문 했던 점은 어짜피 그 나물에 그 밥이기 때문에 그냥 dp에 저장된 값을 return해주면 깔-끔ㅎㅎ

뭔가 그림으로 설명을 하고 싶은데 만들기 어렵고 귀찮으니 코드를 보면서 이해 해주시길 바란다.....

위의 1103 - 게임 문제도 함께 포스팅 할 예정

#include <iostream>
using namespace std;
 
const int MAXSIZE = 17;
int map[MAXSIZE][MAXSIZE], dp[3][MAXSIZE][MAXSIZE];
int N, dab;
 
int dx[] = { 1, 0, 1 };
int dy[] = { 0, 1, 1 };
 
int dfs(int x, int y, int dir) {
    if (dp[dir][y][x]) {
        return dp[dir][y][x];
    }
    int nx, ny;
    if (dir == 2) {
        for (int i = 0; i < 3; i++) {
            nx = x + dx[i]; ny = y + dy[i];
            if (nx >= N || ny >= N || map[ny][nx] == 1)
                return 0;
        }
        nx = x + dx[dir]; ny + dy[dir];
    }
    else {
        nx = x + dx[dir]; ny = y + dy[dir];
        if (ny >= N || nx >= N || map[ny][nx] == 1)
            return 0;        
    }
    nx = x + dx[dir]; ny = y + dy[dir];
    if (ny == N - 1 && nx == N - 1) {
        return 1;
    }
 
    if (dir == 0) {
        dp[dir][y][x] += dfs(x + 1, y, 0);
        dp[dir][y][x] += dfs(x + 1, y, 2);
    }
    else if (dir == 1) {
        dp[dir][y][x] += dfs(x, y + 1, 1);
        dp[dir][y][x] += dfs(x, y + 1, 2);
    }
    else {
        dp[dir][y][x] += dfs(x + 1, y + 1, 0);
        dp[dir][y][x] += dfs(x + 1, y + 1, 1);
        dp[dir][y][x] += dfs(x + 1, y + 1, 2);
    }
    return dp[dir][y][x];
}
 
int main(void) {
    cin >> N;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
 
    cout << dfs(0, 0, 0) << endl;
    return 0;
}