[백준/Baekjoon] 17070 파이프 옮기기 1 C++ :: Implementation

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

17070번: 파이프 옮기기 1

---

1. Logic

같은 위치에 파이프가 위치할 수 있기 때문에 중복 문제가 생기므로 DP를 사용해서 풀이했다.

 

이 문제에서 주의할 점은 지문에서 "꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다." 라는 문장을 잘 읽어야한다.

가로와 세로는 단지 가는 가는 곳만 벽이 아니면 되지만, 대각선 파이프는 옮기는 지점에서 왼쪽, 위쪽이 비어있어야 한다.

이 부분만 잘 짚고 넘어가면 풀이는 어렵지 않다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int dx[3] = {0, 1, 1};
int dy[3] = {1, 1, 0};

int n;
const int INF = 0x3f3f3f3f;

int graph[17][17];
int dp[17][17][3];

int solve(int y, int x, int type) {
    if(y == n-1 && x == n-1) return 1;
    else if(y < 0 || x < 0 || x >= n || y >= n) return 0;

    int &ret = dp[y][x][type];
    if(ret != -1) return ret;
    
    ret = 0;
    
    for(int i = 0; i < 3; i++) {
        if(type == 0 && i == 2) continue;
        else if(type == 2 && i == 0) continue; 
        
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(graph[ny][nx] == 1) continue;
        if(i == 1 && (graph[ny-1][nx] || graph[ny][nx-1])) continue;
        
        ret += solve(ny, nx, i);
    }
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    
    cout << solve(0, 1, 2);
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐