BOJ(C++) / 백준 17070 : 파이프 옮기기 1

백준 17070 : 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

가로

코드

//백준 17070 파이프 옮기기1
#include <iostream>

using namespace std;

int N;
int board[17][17];
int way = 0;

bool isBoard(int i, int j) {
	if (i < 0 || j < 0 || i >= N || j >= N) {
		return false;
	}
	return true;
}

void DFS(int i, int j, int pipeDirection) {
	if (i == N - 1 && j == N - 1) {
		way++;
		return;
	}
	//파이프 가로
	if (pipeDirection == 0) {
		//가로로 이동
		if (isBoard(i, j + 1) == true) {
			if (board[i][j + 1] == 0) {
				DFS(i, j + 1, 0);
			}
		}
		//대각선으로 이동
		if (isBoard(i + 1, j + 1) == true) {
			if (board[i][j + 1] == 0 && board[i + 1][j] == 0 && board[i + 1][j + 1] == 0) {
				DFS(i + 1, j + 1, 2);
			}
		}
	}
	//파이프 세로
	else if (pipeDirection == 1) {
		//세로로 이동
		if (isBoard(i+1, j) == true) {
			if (board[i + 1][j] == 0) {
				DFS(i + 1, j, 1);
			}
		}
		//대각선으로 이동
		if (isBoard(i + 1, j + 1) == true) {
			if (board[i + 1][j] == 0 && board[i][j + 1] == 0 && board[i + 1][j + 1] == 0) {
				DFS(i + 1, j + 1, 2);
			}
		}
	}
	//파이프 대각선
	else if (pipeDirection == 2) {
		//가로로 이동
		if (isBoard(i, j + 1) == true) {
			if (board[i][j + 1] == 0) {
				DFS(i, j + 1, 0);
			}
		}
		//세로로 이동
		if (isBoard(i + 1, j) == true) {
			if (board[i + 1][j] == 0) {
				DFS(i + 1, j, 1);
			}
		}
		//대각선으로 이동
		if (isBoard(i + 1, j + 1) == true) {
			if (board[i + 1][j] == 0 && board[i][j + 1] == 0 && board[i + 1][j + 1] == 0) {
				DFS(i + 1, j + 1, 2);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			board[i][j] = num;
		}
	}

	DFS(0, 1, 0);
	cout << way << "\n";

	return 0;
}

 

설명

pipeDirection과  i, j 위치만으로 어느 위치에 파이프가 놓여져 있는지 확인하여 이동할 수 있다. 

 

이동할 수 있는 방법이 한정적이기 때문에 모든 경우의 수를 나누어 구현할 수 있다. 

 

가로

• pipeDirection이 0일 때(가로)
  • 가로로 이동
  • 대각선으로 이동

 

세로

• pipeDirection이 1일 때(세로)
  • 세로로 이동
  • 대각선으로 이동

 

대각선

• pipeDirection이 2일 때(대각선)
  • 가로로 이동
  • 세로로 이동
  • 대각선으로 이동

다음과 같은 경우의 수가 있다. 

 

이동할 부분의 영역이 이동할 수 있는지 isBoard()함수로 확인하고 Board가 벽인지 아닌지 확인하여 이동시킨다. 

파이프 한쪽 끝이 도달한다면 way를 증가시킨다. 

 

이렇게 이동시킬 수 있는 모든 방법을 구할 수 있다.

 

 

고찰

걸린시간 : 40분

0과 1, i와 j 등 헷갈리는 요소들이 많다. 이 부분들을 정확하게 인지하고 잘못된 부분이 없는지 확인하면서 구현해야 한다.