백준 문제 17070번 파이프 옮기기 1 문제풀이 c++

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

17070번: 파이프 옮기기 1

문제해석 

bfs 또는 dfs를 통해 문제를 풀 수 있는 문제이다.

파이프가 가로 상태일때 이동후 가능한 결과가 2가지

파이프가 세로 상태일때 이동후 가능한 결과가 2가지

파이프가 대각 상태일때 이동후 가능한 결과가 3가지 존재한다.

 

파이프의 끝 부분을을 기준으로 시작해서 한번 이동후 파이프의 모양,파이프의 끝이 위치하는 행과 열을 총 세쌍을 묶어

큐에 넣어주는것을 반복하고 파이프의 끝이 위치하는 행과 열이 끝에 도달하게 되면 ans값을 1씩 늘린다

다만 여기서 위에 그림에서도 나타나 있듯이 색칠된 부분중에 벽이 존재하지 않아야 하기 때문에

조건문에 이 부분을 추가 로 작성해야 한다.

 

만약 dfs로 푼다면 큐에 넣는 행위를 하지 않고 재귀적 방식으로 푸는 것이 가능하다.

실제로 dfs로 풀면 큐를 사용하지않기때문에 메모리와 시간을 아낄수 있었다.

 

bfs 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
int ans=0;
queue < tuple<int,int,int> > q; // 가로0 세로 1 대각2
void solve();
bool inside(int ny,int nx);
int a[16][16];
int n;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    q.push({0,0,1});
    solve();
    cout<<ans;
}
bool inside(int ny,int nx)
{
    if(0<=ny&&ny<n&&0<=nx&&nx<n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void solve(){
    while(!q.empty())
    {
        int flag=get<0>(q.front()); //가로 0 세로 1 대각 2
        int cy=get<1>(q.front());
        int cx=get<2>(q.front());
        q.pop();
        if(cy==n-1&&cx==n-1)
        {
            ans++;
            continue;
        }
        if(flag==0)
        {
            if(inside(cy,cx+1)&&a[cy][cx+1]!=1)
            {
                q.push({0,cy,cx+1});
            }
            if(inside(cy,cx+1)&&a[cy][cx+1]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1&&inside(cy+1,cx)&&a[cy+1][cx]!=1)
            {
                q.push({2,cy+1,cx+1});
            }  
        }
        else if(flag==1)
        {
            if(inside(cy+1,cx)&&a[cy+1][cx]!=1)
            {
                q.push({1,cy+1,cx});
            }
            if(inside(cy+1,cx)&&a[cy+1][cx]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1&&inside(cy,cx+1)&&a[cy][cx+1]!=1)
            {
                q.push({2,cy+1,cx+1});
            }
        }
        else if(flag==2)
        {
            if(inside(cy,cx+1)&&a[cy][cx+1]!=1)
            {
                q.push({0,cy,cx+1});
            }
            if(inside(cy+1,cx)&&a[cy+1][cx]!=1)
            {
                q.push({1,cy+1,cx});
            }
            if(inside(cy,cx+1)&&a[cy][cx+1]!=1&&inside(cy+1,cx)&&a[cy+1][cx]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1)
            {
                q.push({2,cy+1,cx+1});
            }
        }
    }
}

dfs 코드

#include <iostream>
#include <algorithm>
using namespace std;
int ans=0;
void solve(int flag,int cy,int cx);
bool inside(int ny,int nx);
int a[16][16];
int n;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    solve(0,0,1);
    cout<<ans;
}
bool inside(int ny,int nx)
{
    if(0<=ny&&ny<n&&0<=nx&&nx<n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void solve(int flag,int cy,int cx){
    if(cy==n-1&&cx==n-1)
    {
        ans++;
        return;
    }
    if(flag==0)
    {
        if(inside(cy,cx+1)&&a[cy][cx+1]!=1)
        {
            solve(0,cy,cx+1);
        }
        if(inside(cy,cx+1)&&a[cy][cx+1]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1&&inside(cy+1,cx)&&a[cy+1][cx]!=1)
        {
            solve(2,cy+1,cx+1);
        }  
    }
    else if(flag==1)
    {
        if(inside(cy+1,cx)&&a[cy+1][cx]!=1)
        {
            solve(1,cy+1,cx);
        }
        if(inside(cy+1,cx)&&a[cy+1][cx]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1&&inside(cy,cx+1)&&a[cy][cx+1]!=1)
        {
            solve(2,cy+1,cx+1);
        }
    }
    else if(flag==2)
    {
        if(inside(cy,cx+1)&&a[cy][cx+1]!=1)
        {
            solve(0,cy,cx+1);
        }
        if(inside(cy+1,cx)&&a[cy+1][cx]!=1)
        {
            solve(1,cy+1,cx);
        }
        if(inside(cy,cx+1)&&a[cy][cx+1]!=1&&inside(cy+1,cx)&&a[cy+1][cx]!=1&&inside(cy+1,cx+1)&&a[cy+1][cx+1]!=1)
        {
            solve(2,cy+1,cx+1);
        }
    }
}