[백준][백트래킹] 1189 컴백홈 c++ 구현

목차

1. 문제
2. 코드 구현 방향
3. 코드 구현

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

문제

 

 

코드 구현 방향

백트래킹을 통해 탐색을 하였다. 

거리가 도달할 경우 종료해 가지치기를 해 주었다.

 

코드 구현

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
using namespace std;

int R, C, K;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int cnt = 0;
int startx, starty, endx, endy;
char board[7][7] = { '.', };
int visit[7][7] = { 0 };

void print() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cout << visit[i][j] << " ";
		}
		cout << "\n";
	}
}

void dfs(int x, int y) {
	//print();
	if (visit[y][x] == K) {
		if (x == endx && y == endy) {
			cnt++;
		}
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (ny <0 || ny > R - 1 || nx < 0 || nx > C - 1)
			continue;
		if (visit[ny][nx] || board[ny][nx] == 'T')
			continue;
		visit[ny][nx] = 1+visit[y][x];
		dfs(nx, ny);
		visit[ny][nx] = 0;
	}

}
int main() {
	cin >> R >> C >> K;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> board[i][j];
		}
	}
	startx = 0;
	starty = R - 1;
	endx = C - 1;
	endy = 0;
	visit[starty][startx] = 1;
	dfs(startx, starty);


	cout << cnt;
	
}