17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)

문제 풀이

 

파이프를 옮기면서 목적지까지 도달할 수 있는 경우의 수를 고르는 문제입니다. 파이프의 좌표에 유의하여 문제를 풀이하였습니다. 우선 파이프의 초기 좌표는 pipe1 = (1,1), pipe2 = (1,2)입니다.

이 때 파이프를 옮기게 되면, pipe1은 항상 pipe2의 위치로 이동하게 됩니다.

pipe2의 경우, 각각 가로로 있는 경우와 세로로 있는 경우, 대각선으로 있는 경우를 고려하여 좌표를 이동시켜 주면 됩니다. 벽이 있는 경우와 지도를 탈출하는 경우에 주의합니다. 이 후 pipe2가 목적지에 도착하였다면, 결과값에 추가시켜 줍니다.

 

 

코드

 

#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
int n, ans;
int arr[17][17];
int dx[] = {0, 1, 1};
int dy[] = {1, 1, 0};
 
 
void movePipe(pair<int,int> p1, pair<int,int> p2) {
 
    if (p2 == make_pair(n, n)) {
        ans++;
    }
 
    pair<int, int> tmp_p2;
 
    for (int i = 0; i < 3; i++) {
        tmp_p2 = p2;
 
        if ((p1.first == p2.first) && (i == 2)) continue;
        else if ((p1.second == p2.second) && (i == 0)) continue;
 
        tmp_p2.first += dx[i]; tmp_p2.second += dy[i];
        if (tmp_p2.first <= n && tmp_p2.second <= n && tmp_p2.first > 0 && tmp_p2.second > 0 && arr[tmp_p2.first][tmp_p2.second] == 0) {
            if (i == 1) {
                int x1 = p2.first + dx[0], y1 = p2.second + dy[0], x2 = p2.first + dx[2], y2 = p2.second + dy[2];
                if ((x1 <= n && x1 > 0 && y1 <= n && y1 > 0) && (arr[x1][y1] == 1)) continue;
                if ((x2 <= n && x2 > 0 && y2 <= n && y2 > 0) && (arr[x2][y2] == 1)) continue;
                movePipe(p2, tmp_p2);
            }
            else {
                movePipe(p2, tmp_p2);
            }
        }
    }
}
 
int main() {
 
    ans = 0;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
 
    pair<int, int> init_p1 = { 1,1 }, init_p2 = { 1,2 };
 
    movePipe(init_p1, init_p2);
    cout << ans << '\n';
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

17070번: 파이프 옮기기 1