백준 17070번 파이프 옮기기 1 C++ DFS

리뷰

 

0, 1 좌표에서 파이프를 옮겨 n - 1, n - 1 좌표까지 이동 가능한 모든 경로를 구하는 문제

 

문제 풀이

1. 전역 변수로 변의 크기 n, 정답용 변수 ans, 맵을 나타낼 lst 배열, 방문 처리를 나타낼 v 배열, 방향 배열을 초기화 한다.
2. n값을 입력 받고 ans를 0으로 초기화 한 뒤에 n * n크기의 맵을 lst에 초기화 해준다.
3. 0, 0과 0, 1을 방문 처리해 주고 0, 1 좌표 및 방향 배열 인덱스는 0 (오른쪽)으로 dfs를 시작해 준다.
4. dfs의 매개변수로는 현재 좌표 x, y값과 방향 위치인 dir을 받는다.
5. 기저 조건으로 x, y 좌표가 n - 1일때 ans를 증가시키고 리턴을 해준다.
6. 현재 방향 인덱스에 -1 ~ 1범위로 더해주고 만약 인덱스 범위를 벗어난다면 continue 처리를 해준다.
7. 다음 좌표는 현재 방향으로 진행하게 되며, 맵의 범위 안에 있고, 방문하지 않았고, 맵이 1이 아닌경우 이동한다.
8. 다음 좌표를 방문처리 하고, 다음 좌표 및 변경된 방향을 재귀 돌려준다.
9. 예외 사항으로 만약 방향 인덱스가 1 즉 대각선 이동일 경우 이동 위치의 위와 왼쪽을 탐색해 1이 있는지 추가로 확인해 주어야 한다, 1이 존재한다면 continue처리
10. 재귀를 빠져나오며 방문처리 했던 것을 다시 풀어주면 된다.
11. 모든 재귀를 마치고 나서 ans 값을 출력해 주면 된다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>

using namespace std;

int n, ans;
int lst[16][16]; 
int v[16][16] = { 0, }; 
int dx[] = { 0, 1, 1 }; // 방향은 우측 우측아래 아래로 이동해야 한다.
int dy[] = { 1, 1, 0 };

void dfs(int x, int y, int dir) {
	if (x == n - 1 && y == n - 1) { // 기저조건
		ans++;
		return;
	}
	for (int i = -1; i < 2; i++) { // 방향 인덱스 -1, 0, 1 적용
		int ndir = dir + i; // 다음 방향 인덱스
		if (ndir < 0 || 2 < ndir) continue; // 방향 인덱스 범위 벗어나면 continue
		int nx = x + dx[ndir], ny = y + dy[ndir]; // 다음 좌표
		if (nx < n && ny < n && !v[nx][ny] && !lst[nx][ny]) { // 범위, 조건 탐색
			if (ndir == 1 && (lst[nx][ny - 1] || lst[nx - 1][ny])) continue; // 대각선인 경우 예외 처리 필요
			v[nx][ny] = 1;
			dfs(nx, ny, ndir);
			v[nx][ny] = 0;
		}
	}
}

int main() {
	cin >> n;
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
		}
	}
	v[0][0] = 1;
	v[0][1] = 1;
	dfs(0, 1, 0);
	cout << ans;
}