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

#문제

17070번: 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

 

---

#접근방법

이 문제는 방향성을 고려하여 파이프를 옮길 수 있는지 여부를 파악해서 dfs로 탐색을 해주면 된다.

반응형

---

#풀이

#include <stdio.h>

int arr[20][20];
int n;

void dfs(int x, int y, int direction){
	arr[x][y]++;
	
	if(direction==0 || direction==2){
		if(y<n && arr[x][y+1]!=-1)
			dfs(x,y+1,0);
	}
	if(direction==1 || direction==2){
		if(x<n && arr[x+1][y]!=-1)
			dfs(x+1,y,1);
	}
	if(x<n && y<n && arr[x][y+1]!=-1 && arr[x+1][y]!=-1 && arr[x+1][y+1]!=-1)
		dfs(x+1,y+1,2);
	
	return;
}

int main(){
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&arr[i][j]);
			if(arr[i][j]==1) arr[i][j] = -1;
		}
	
	//0:가로, 1:세로, 2:대각선
	dfs(1,2,0);
	
	if(arr[n][n]==-1) arr[n][n] = 0;
	
	printf("%d",arr[n][n]);
	
	return 0;
}

 

n을 입력받고 n*n 크기의 칸을 배열로 입력받는다. 모든 경우의 수를 구해야 하므로 이동할 수 있으면 배열에 +1을 하여 누적값으로 계산을 하기 위해서 입력값이 1이면 -1로 바꿔주었다.

 

배열을 입력받고 dfs(1,2,0)함수를 호출해준다. 1,2는 파이프의 오른쪽 좌표이고, 0은 방향이 가로라는 뜻이다. 0은 가로, 1은 세로, 2는 대각선으로 생각하였다.

 

dfs함수에서 arr[x][y]++을 해주어서 갈 수 있는 좌표에 값을 누적시켜주었다.

 

direction이 0또는 2이고 오른쪽으로 이동할 수 있으면 dfs(x,y+1,0)을 호출하였고,

direction이 1또는 2이고 밑으로 이동할 수 있으면 dfs(x+1,y,1)을 호출하였고,

direction과 상관없이 대각선으로 이동할 수 있으면 dfs(x+1,y+1,2)을 호출하였다.

 

arr[n][n]에 벽이 있으면 -1이 저장되어있으므로 arr[n][n]에 0을 넣어서 예외처리를 해주었다.

 

arr[n][n]을 출력하면 정답이다.

---

#성능

---

#정리

방향성에 따라서 적절한 조건문과 탐색을 할 수 있는 것,

 

이를 구현할 수 있는 구현력이 있으면 풀 수 있는 문제였다.