[DFS] BJ17070 파이프 옮기기 1

문제 출처: https://www.acmicpc.net/problem/17070

 

Solution

• DFS로 맵을 탐색하면서 목적지를 만나면 가능 경로 회수를 늘려준다.

Point

• 이동 방식이 조금 특이한데, 우선 칸을 2개 차지하면서 이동하는 것 같으나 사실 앞에 차지한 칸만 고려해주면 되고, 가로나 세로 방향일 때는 방향을 유지하거나 대각선 방향으로만 꺾을 수 있다. 또, 대각선으로 이동할 때는 총 네 칸이 비어있어야 이동 가능하다.
• 현재 방향 상태에서 이동 가능한 다음 방향을 nd로 정의해서 사용했다.
• 맵의 가장 자리를 모두 1로 채워줘서 해당 방향에 벽이 있는 것처럼 맵을 구성해 범위를 체크한다.

---

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N;
int dr[] = { 0, 1, 1 }; // →, ↓, ↘
int dc[] = { 1, 0, 1 };
vector<int> nd[3] = { {0, 2}, {1, 2}, {0, 1, 2} };
int visit[18][18];
int map[18][18];
int result;

void input() {
    result = 0;
    memset(map, 1, sizeof(map));
    cin >> N;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> map[i][j];
}

bool IsWay(int r, int c, int d) {
    if (map[r][c]) return false;
    if ((d == 2) && (map[r][c - 1] || map[r - 1][c])) return false;
    return true;
}

void dfs(int cr, int cc, int cd) {
    visit[cr][cc] = true;
    for(int i = 0; i < nd[cd].size(); i++){
        int nr = cr + dr[nd[cd][i]];
        int nc = cc + dc[nd[cd][i]];
        if (!visit[nr][nc] && IsWay(nr, nc, nd[cd][i])) {
            if (nr == N && nc == N) {result++; return;}
            dfs(nr, nc, nd[cd][i]);
            visit[nr][nc] = false;
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    input();
    dfs(1, 2, 0);
    cout << result << endl;
}