백준[17070] 파이프 옮기기

본 문제의 출처는 아래에서 확인할 수 있다.

 

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

 

이 문제는 인증된 문제집의 '삼성 A형'에서 확인할 수 있다.

 

N의 크기가 매우작으며 오른쪽과 아래로 밖에 이동하지 않는다. 연결할 수 있는 모든 경우를 탐색하도록 한다. 필자는 BFS를 사용하였다.

 

방향 즉, 파이프 연결에 따른 이동 방법에 따라 파이프를 모두 연결하여 탐색을 진행하는데 여기서는 중복된 모든 경우를 봐야하기 때문에 방문체크여부를 할 필요가 없다. 큐에 연결가능한 경우를 모두 넣어 조건에 맞게 진행하면 쉽게 해결할 수 있다.

 

방향에 따른 처리 간소화하여 코드를 작성할 수 있다. 

 

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include<bitset>
#include<set>
 
using namespace std;
 
struct info {
    int a=0, b=1, c=0,d=1;
};
 
int n, arr[18][18],ans;
info in;
queue<info> q;
 
bool r(int a, int b) {
    if (a >= 0 && a < n && b >= 0 && b < n) return true;
    else return false;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    q.push(in);
    while (!q.empty()) {
        int x, y, cnt, dir;
        x = q.front().a;
        y = q.front().b;
        cnt = q.front().c;
        dir = q.front().d;
        if (x == n - 1 && y == n - 1) ans++;
        //cout << x << "  " << y << "  " << cnt << "  " << dir <<endl;
        q.pop();
        if (dir == 1) {
            if (arr[x][y + 1] == 0 && r(x, y + 1)) {
                //printf("1  ???\n");
                in.a = x, in.b = y + 1, in.c = cnt + 1, in.d = 1;
                q.push(in);
            }
            if (arr[x + 1][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x][y + 1] == 0 && r(x + 1, y + 1)) {
                in.a = x + 1, in.b = y + 1, in.c = cnt + 1, in.d = 3;
                q.push(in);
            }
        }
 
        else if (dir == 2) {
            if (arr[x + 1][y] == 0 && r(x + 1, y)) {
                in.a = x + 1, in.b = y, in.c = cnt + 1, in.d = 2;
                q.push(in);
            }
            if (arr[x + 1][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x][y + 1] == 0 && r(x + 1, y + 1)) {
                in.a = x + 1, in.b = y + 1, in.c = cnt + 1, in.d = 3;
                q.push(in);
            }
        }
 
        else if (dir == 3) {
            if (arr[x + 1][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x][y + 1] == 0 && r(x + 1, y + 1)) {
                in.a = x + 1, in.b = y + 1, in.c = cnt + 1, in.d = 3;
                q.push(in);
            }
            if (arr[x + 1][y] == 0 && r(x + 1, y)) {
                in.a = x + 1, in.b = y, in.c = cnt + 1, in.d = 2;
                q.push(in);
            }
            if (arr[x][y + 1] == 0 && r(x, y+1)) {
                in.a = x, in.b = y + 1, in.c = cnt + 1, in.d = 1;
                q.push(in);
            }
        }
    }
    printf("%d", ans);
    return 0;
}