[C/C++] 17070: 파이프 옮기기 1

17070: 파이프 옮기기 문제

 

 이 문제도 (1,2)를 시작해서 graph를 탐색하며 (n,n)까지 가는 경우의 수를 구하는 문제이기 때문에 그래프 탐색 이론을 사용해야한다. 내가 구현한 방식으로는 현재 지점이 이전 지점에서 어떻게 왔냐 (1.가로 2.대각선 3.세로)에 따라서 탐색의 방향을 정했기 때문에 2차원 배열을 이용하여 queue를 사용한 BFS보다는 DFS가 훨씬 쉽다고 판단하여 DFS를 이용하여 문제를 풀었다.

 

 DFS에서 이전 지점에서 어떻게 왔냐에 따라 아래 코드처럼 나누었다.

void DFS(int n,int x,int y)
{
  if(previous[y][x]==1) //오른쪽으로 감
     GoRight(n,x,y);
  
  if(previous[y][x]==2) //대각선으로 감
     GoDiagonal(n,x,y);
  
  if(previous[y][x]==3) //아래쪽으로 감
     GoDown(n,x,y);
}

 

 그리고 Go~~로 시작하는 함수들은 그 형태를 모두 비슷하게 맞추었는데 변수 nx, ny를 통해 범위를 벗어나지는 않는지 혹은 벽이 있는 공간인지를 확인하여 갈 수 있는 곳이라면 끝지점을 도달했는지를 판단하고 다시 DFS함수를 호출하는  CheckEnd 함수를 사용하였다.

void CheckEnd(int n,int y,int x)
{
  if(y==n&&x==n)
  {
    count++;
    return;
  }
  else
    DFS(n,x,y);    
}

 

 

아래는 전체 소스코드이다!

#include <stdio.h>
#include <string.h>

int graph[17][17];

int previous[17][17]; //어떤 방법으로 왔냐 1:가로 2:대각선 3:세로
int count=0;
//DFS로 풀어야할듯함
void DFS(int n,int x,int y);


void CheckEnd(int n,int y,int x)
{
  if(y==n&&x==n)
  {
    count++;
    return;
  }
  else
    DFS(n,x,y);    
}

void GoRight(int n,int x, int y)
{
  int nx,ny;
  nx=x+1,ny=y;
  if(nx<=n && graph[ny][nx]!=1) //가로로 갈 수 있는지
  {
    previous[ny][nx]=1;
    CheckEnd(n,ny,nx);
  }
  nx=x+1,ny=y+1;
  if(nx<=n && graph[ny][nx]!=1 && ny<=n &&graph[ny-1][nx]!=1 && graph[ny][nx-1]!=1)
  {
    previous[ny][nx]=2;
    CheckEnd(n,ny,nx);
  }
}

void GoDiagonal(int n,int x, int y)
{
  int nx,ny;
  nx=x+1,ny=y;
  if(nx<=n && graph[ny][nx]!=1) //가로로 갈 수 있는지
  {
    previous[ny][nx]=1;
    CheckEnd(n,ny,nx);
  }
  nx=x+1,ny=y+1;
  if(nx<=n && graph[ny][nx]!=1 && ny<=n &&graph[ny-1][nx]!=1 && graph[ny][nx-1]!=1)
  {
    previous[ny][nx]=2;
    CheckEnd(n,ny,nx);
  }
  nx=x,ny=y+1;
  if(nx<=n && graph[ny][nx]!=1 && ny<=n) //세로로 갈 수 있는지
  {
    previous[ny][nx]=3;
    CheckEnd(n,ny,nx);
  }
}

void GoDown(int n,int x,int y)
{
  int nx,ny; 
  nx=x+1,ny=y+1;
  if(nx<=n && graph[ny][nx]!=1 && ny<=n &&graph[ny-1][nx]!=1 && graph[ny][nx-1]!=1)
  {
    previous[ny][nx]=2;
    CheckEnd(n,ny,nx);
  }
  nx=x,ny=y+1;
  if(nx<=n && graph[ny][nx]!=1 && ny<=n) //세로로 갈 수 있는지
  {
    previous[ny][nx]=3;
    CheckEnd(n,ny,nx);
  }
}

void DFS(int n,int x,int y)
{
  if(previous[y][x]==1) //오른쪽으로 감
     GoRight(n,x,y);
  
  if(previous[y][x]==2) //대각선으로 감
     GoDiagonal(n,x,y);
  
  if(previous[y][x]==3) //아래쪽으로 감
     GoDown(n,x,y);
}

int main(void)
  {
    int n;
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
      {
        for(int i=1;i<=n;i++)
          {
            scanf("%d",&graph[j][i]);
          }
      }        
    previous[1][2]=1;    
    DFS(n,2,1);
    printf("%d",count);
   
  }