백준 17069, 17070 파이프옮기기

파이프 옮기기1, 파이프 옮기기2 문제풀이

파이프옮기기1

처음에 0,0에서 0,1로 가는 파이프가 N-1,N-1까지 가는 경우의 수를 출력하는 문제.
N제한이 16이기때문에 최악의 경우 경우의 수는 3^16 = 43,046,721이다.
브루트 포스로 풀 수 있다.
매번 다음 위치와 파이프의 모양을 매개변수로 줘서 재귀적으로 구현했다.

파이프가 대각선으로 있을 땐 현재 위치 오른쪽, 밑의 칸에도 영향을 주므로 주의해야한다. 내 코드엔 check_wall함수를 이용해 한번 더 체크해주었다.

어렵지 않았던 문제.

파이프옮기기1 소스

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
int ma[20][20];
int x_index[3]={0,1,1};
int y_index[3]={1,1,0};

bool check(int nx,int ny){
	return ma[nx][ny]==0&&nx<n&&nx>=0&&ny<n&&ny>=0;
}
bool check_wall(int nx,int ny){
	return ma[nx-1][ny]==0&&ma[nx][ny-1]==0;
}
int go(int x,int y,int pipe){
	if(x==n-1&&y==n-1){
		return 1;
	}
	int ans=0;
	if(pipe==0){//가로
		for(int i=0;i<2;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==0)
					ans+=go(nx,ny,0);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
			}
		}
	}
	if(pipe==1){//세로
		for(int i=1;i<3;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==2)
					ans+=go(nx,ny,1);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
			}
		}

	}
	if(pipe==2){//대각선
		for(int i=0;i<3;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==0)
					ans+=go(nx,ny,0);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
				if(i==2)
					ans+=go(nx,ny,1);
			}
		}
	}
	return ans;	
}


int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>ma[i][j];
		}
	}
	cout<<go(0,1,0)<<'\n';
	return 0;

}

파이프옮기기2

전 브루트포스로 구현한 소스에 memoization기법을 이용해 값을 저장해주기만 하면 된다.
파이프모양에 따라 값이 달라지므로 2차원배열에 파이프의 모양 하나를 더 추가해주어야 한다.
주의할 점은 정답이 21억이 넘어가는 경우가 있기 때문에 int를 long long으로 바꾸어주어야 한다.

오타나 지적, 질문 환영합니다.

파이프옮기기2 소스

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
int ma[40][40];
int x_index[3]={0,1,1};
int y_index[3]={1,1,0};
bool visited[40][40][3]={0};
long long answer[40][40][3]={0};
bool check(int nx,int ny){
	return ma[nx][ny]==0&&nx<n&&nx>=0&&ny<n&&ny>=0;
}
bool check_wall(int nx,int ny){
	return ma[nx-1][ny]==0&&ma[nx][ny-1]==0;
}
long long go(int x,int y,int pipe){
	if(visited[x][y][pipe]==true)
		return answer[x][y][pipe];
	if(x==n-1&&y==n-1){
		return 1;
	}
	visited[x][y][pipe]=true;
	long long ans=0;
	if(pipe==0){//가로
		for(int i=0;i<2;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==0)
					ans+=go(nx,ny,0);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
			}
		}
	}
	if(pipe==1){//세로
		for(int i=1;i<3;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==2)
					ans+=go(nx,ny,1);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
			}
		}

	}
	if(pipe==2){//대각선
		for(int i=0;i<3;i++){
			int nx=x+x_index[i];
			int ny=y+y_index[i];
			if(check(nx,ny)){
				if(i==0)
					ans+=go(nx,ny,0);
				if(i==1&&check_wall(nx,ny))
					ans+=go(nx,ny,2);
				if(i==2)
					ans+=go(nx,ny,1);
			}
		}
	}
	answer[x][y][pipe]=ans;
	return answer[x][y][pipe];	
}


int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>ma[i][j];
		}
	}
	cout<<go(0,1,0)<<'\n';
	return 0;

}