[ 백준 17070 ] 파이프 옮기기 1 (C++)

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

17070번: 파이프 옮기기 1

 

문제를 읽고 dfs로 해결할 수 있겠다는 생각을 했다. 파이프는 가로, 세로, 대각선 모양만 허용되고 각 경우마다 움직일 수 있는 방법이 정해져 있다. 이를 각 케이스마다 구현해주면 된다. 목표 지점이 벽인 경우만 주의하면 된다.

 

이동 가능한 모든 경우의 수

DFS 함수 형태

void dfs(int row, int col, int type, int* cnt)

row: 이동 방향 머리의 행 인덱스
col: 이동 방향 머리의 열 인덱스
type: 파이프 타입(가로: 0, 세로: 1, 대각선: 2)
cnt: 목적지까지 도달 가능한 경우의 수

 

이동 방향 머리의 행, 열 인덱스만 봐도 되는 이유는 현재 머리의 위치가 다음 꼬리의 위치와 일치하기 때문이다. Type 변수가 핵심인데, 이 변수로 이동 가능한 모든 경우의 수를 표현할 수 있다. 

 

1. DFS 종료 조건

1. 파이프 머리가 벽에 부딪히면 끝
2. 대각선인 경우 세 칸 검사, 만약 하나라도 벽이 있으면 끝
3. 목표 지점인 경우 cnt++ 

2. 탐색 조건

type(0) : 가로인 경우 가로, 대각선으로 이동 가능
→ type(0) : col++
→ type(2) : row++ col++

type(1) : 세로인 경우 세로, 대각선으로 이동 가능
→ type(1) : row++
→ type(2) : row++ col++

type(2) : 대각선인 경우 가로, 세로, 대각선으로 이동 가능
→ type(0) : col++
→ type(1) : row++
→ type(2) : row++ col++

 

 

이를 그대로 코드로 구현하면 된다. 정답 코드는 아래와 같다. 

 

#include <iostream>
#include <algorithm>
#define GOAL 2
using namespace std;

int N, map[16][16], visit[16][16];

bool check(int row, int col) {
	// map 범위에 있으면 참, 아니면 거짓
	if (row >= 0 && col >= 0 && row < N && col < N)
		return true;
	
	return false;
}

void dfs(int row, int col, int type, int* cnt) {
	// 벽이면 끝
	if(map[row][col] == 1) return;

	// 대각선은 세 칸 검사
	if (type == 2) {
		if (map[row - 1][col] == 1) return;
		if (map[row][col - 1] == 1) return;
	}

	// GOAL이면 cnt++
	if (map[row][col] == GOAL) {
		(*cnt)++;
		return;
	}

	if (type == 0) {
		// 가로인 경우
		if (check(row, col + 1)) dfs(row, col + 1, 0, cnt);
		if (check(row + 1, col + 1)) dfs(row + 1, col + 1, 2, cnt);
	}
	else if (type == 1) {
		// 세로인 경우
		if (check(row + 1, col)) dfs(row + 1, col, 1, cnt);
		if (check(row + 1, col + 1)) dfs(row + 1, col + 1, 2, cnt);
	}
	else if (type == 2) {
		// 대각선인 경우
		if (check(row, col + 1)) dfs(row, col + 1, 0, cnt);
		if (check(row + 1, col)) dfs(row + 1, col, 1, cnt);
		if (check(row + 1, col + 1)) dfs(row + 1, col + 1, 2, cnt);
	}
}

int main() {

	cin >> N;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	// 목표 지점이 벽인 경우 고려
	if (map[N - 1][N - 1] != 1)
		map[N - 1][N - 1] = GOAL;

	int cnt = 0;

	dfs(0, 1, 0, &cnt);

	cout << cnt << endl;

	return 0;
}