(c++)백준 17070번: 파이프 옮기기 1

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

[풀이]

dfs를 이용해서 풀 수 있는 문제였다.

오른쪽, 아래, 오른쪽 아래 대각선 방향으로만 움직이므로 파이프의 오른쪽 부분(이동방향쪽 한 칸)만 고려하면 된다.

일반적인 경로탐색에서 방향을 세 가지로 바꾸고 조건을 추가해주었다.

1. (N-1,N-1)에 도달하면 cnt++

2. 가로, 세로 방향일 때 그 다음에 이동 가능한 방향인지 확인

3. 대각선 방향일 때 오른쪽, 아래, 오른쪽 대각선 아래 모두 벽이 아닌지 확인

4. 다음 칸으로 이동

#include <iostream>
using namespace std;

int N;
int Map[16][16];
bool visited[16][16];
int cnt = 0;
const int dxy[][2] = { {0,1},{1,0},{1,1} };//오른쪽, 아래, 대각선

void dfs(int x, int y, int d) {
	if (x == N - 1 && y == N - 1) {
		cnt++;
		return;
	}
	for (int i = 0; i < 3; i++) {
		//가능한 이동 방법 아니면 패스 
		if ((d == 0 && i == 1) || (d == 1 && i == 0))
			continue;
		int nx = x + dxy[i][0];
		int ny = y + dxy[i][1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N || Map[nx][ny] == 1)
			continue;
		//대각선 방향인 경우
		if (i == 2) {
			if (Map[x + 1][y] == 1 || Map[x][y + 1] == 1)
				continue;
		}
		if (visited[nx][ny] == false) {
			visited[nx][ny] = true;
			dfs(nx, ny, i);
			visited[nx][ny] = false;
		}
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
		}
	}
	//처음 시작은 (0,1)에서 가로방향
	dfs(0, 1, 0);
	cout << cnt << '\n';
}

int main() {
	solution();
	return 0;
}

 

+ 각각 방향마다 가보는 방향 달리해서 dfs

visited배열 쓰지 않는 방법, 시간이 더 단축됐다.

#include <iostream>
using namespace std;

int N;
int House[17][17];
const int dxy[][2] = { {0,1},{1,1},{1,0} };//오른쪽 대각선 아래
int Cnt = 0;

void dfs(int x, int y, int d) {
	if (x == N && y == N) {
		Cnt++;
		return;
	}
	//오른쪽 방향일 때
	if (d == 0) {
		//오른쪽, 오른쪽 대각선 가보기
		for (int i = 0; i <= 1; i++) {
			int nx = x + dxy[i][0];
			int ny = y + dxy[i][1];
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			//대각선 방향이면 오른쪽, 아래 다 비어있어야 함
			if (i == 1) {
				if (House[x + 1][y] == 1 || House[x][y + 1] == 1)
					continue;
			}
			//빈칸이면
			if (House[nx][ny] == 0)
				dfs(nx, ny, i);
		}
	}
	//오른쪽 대각선 방향일 때
	else if (d == 1) {
		//오른쪽, 오른쪽 대각선, 아래 가보기
		for (int i = 0; i <= 2; i++) {
			int nx = x + dxy[i][0];
			int ny = y + dxy[i][1];
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			//대각선 방향이면 오른쪽, 아래 다 비어있어야 함
			if (i == 1) {
				if (House[x + 1][y] == 1 || House[x][y + 1] == 1)
					continue;
			}
			//빈칸이면
			if (House[nx][ny] == 0)
				dfs(nx, ny, i);
		}
	}
	//아래 방향일 때
	else if (d == 2) {
		//아래, 오른쪽 대각선 가보기
		for (int i = 2; i >= 1; i--) {
			int nx = x + dxy[i][0];
			int ny = y + dxy[i][1];
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			//대각선 방향이면 오른쪽, 아래 다 비어있어야 함
			if (i == 1) {
				if (House[x + 1][y] == 1 || House[x][y + 1] == 1)
					continue;
			}
			//빈칸이면
			if (House[nx][ny] == 0)
				dfs(nx, ny, i);
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> House[i][j];
		}
	}
	dfs(1, 2, 0);
	cout << Cnt << '\n';
	return 0;
}