[백준] 파이프 옮기기 1 17070번 (c++)

출처 : 17070번: 파이프 옮기기 1 (acmicpc.net)

17070번: 파이프 옮기기 1

풀이 방법

bfs로 파이프의 머리 부분의 좌표와 가로로, 대각선, 세로 상태를 queue에 넣어 주었다.

각 상태에 따라  can_right, can_diagonal, can_bottom를 사용하여 이동할 수 있는지 판별 후

이동할 수 있으면 queue에 넣어주었다. 그리고 파이프의 머리가 도착지점에 도달하면 cnt++을 해주어 답을 찾았다.

// 1600
#include <bits/stdc++.h>
using namespace std ;

int N, cnt = 0;
int house[16][16];


int can_right(int y, int x, int state) {
    if (state == 0 || state == 1) {
        if (y < N && x < N) {
            if (house[y][x + 1] == 0)
                return 1;
        }
    }
    return 0;
}

int can_diagonal(int y, int x, int state) {
    if (y + 1 < N && x + 1 < N) {
        if (house[y][x + 1] == 0) {
            if (house[y + 1][x + 1] == 0) {
                if (house[y + 1][x] == 0) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int can_bottom(int y, int x, int state) {
    if (y + 1 < N && x < N) {
        if (state == 1 || state == 2) {
            if (house[y + 1][x] == 0) {
                return 1;
            }
        }
    }
    return 0;
}

void bfs() {
    queue<pair<pair<int, int>, int>> q; // 파이프의 앞점 , 파이프의 상태 0 : 가로 1 : 대각선 2 : 세로
    q.push(make_pair(make_pair(0, 1), 0));

    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int state = q.front().second;
        q.pop();
        if (y == N-1 && x == N-1) {
            cnt++;
        }
        if (can_right(y, x, state)) {
            q.push(make_pair(make_pair(y, x + 1), 0));
        }
        if (can_diagonal(y, x, state)) {
            q.push(make_pair(make_pair(y + 1, x + 1), 1));
        }
        if (can_bottom(y, x, state)) {
            q.push(make_pair(make_pair(y + 1, x), 2));
        }
    }
}


int main () {
    cin >> N;
    for (int i = 0;i < N;i++) {
        for (int k = 0;k < N;k++) {
            cin >> house[i][k];
        }
    }

    bfs();
    cout << cnt;
    return 0;
}