개요

백준 1189번: 컴백홈

• 입력
  첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

• 출력
  첫 줄에 거리가 K인 가짓수를 출력한다.

접근 방법

1. 기본적으로 DFS방식을 통해 다음칸을 탐색하고 탐색이 끝나면 방문여부를 다시 초기화 시켜줘서
   해당 정점을 다시 방문토록 백트래킹방식으로 구현하였다.
   (1->2->3->4) 방문 후, (1->2->5->6) 이런식으로 방문 할 수 있어야하는데,
   DFS방식으로 초기화를 안시키면 1,2,3,4는 방문 후 다시 못돌아간다.

2. 조심해야 할 부분은 왼쪽아래가 시작점, 오른쪽 위가 도착점이다.
   (h-1,0)에서 시작하고, (0,R-1)에서 끝나야한다.

3. 시작칸 체크해줘야한다.

	//시작칸 방문처리해줘야함.
	visited[h][w] = true;
	//다음칸만 T인지 탐색하면 안 되고 시작칸이 T일수도 있다. return
	if (Road[h][w]== 'T') {
		return;
	}

3. 상하좌우를 일일이 if else로 체크하지않고 반복문을 통해 체크하였다.

	for (int i = 0; i < 4; i++) {
		//다음 가로값
		int nextH = h + dx[i];
		//다음 세로값
		int nextW = w + dy[i];

		//범위 바깥이면 continue
		if (nextH<0||nextW<0||nextH >= height || nextW >= width) continue;
		//다음칸 T라면 continue
		if (Road[nextH][nextW] == 'T') continue;
		//방문이미 했다면 continue
		if (visited[nextH][nextW]) continue;
		//조건 다 지나왔다면 방문처리해준 후
		visited[nextH][nextW] = true;
		//다음 백트래킹 실행
		Backtracking(nextH, nextW, length + 1);
		//백트래킹 하고 전단계로 돌아오면 방문처리 초기화해줌
		visited[nextH][nextW] = false;
	}

전체 코드

#include<iostream>
#include<vector>

using namespace std;
char Road[6][6];
int height=0,width=0,targetDistance = 0,ans=0;
bool visited[6][6];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void Input() {
	cin >> height >> width>> targetDistance;
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> Road[i][j];
		}
	}

}

void Backtracking(int h, int w,int length) {
	//시작칸 방문처리해줘야함.
	visited[h][w] = true;
	//다음칸만 T인지 탐색하면 안 되고 시작칸이 T일수도 있다. return
	if (Road[h][w]== 'T') {
		return;
	}
	//만약 목적지 도착시
	if (h == 0 && w == width-1) {
		//길이가 K랑 같다면 ans증가시키기
		if (length == targetDistance) ans++;
		return;
	}

	for (int i = 0; i < 4; i++) {
		//다음 가로값
		int nextH = h + dx[i];
		//다음 세로값
		int nextW = w + dy[i];

		//범위 바깥이면 continue
		if (nextH<0||nextW<0||nextH >= height || nextW >= width) continue;
		//다음칸 T라면 continue
		if (Road[nextH][nextW] == 'T') continue;
		//방문이미 했다면 continue
		if (visited[nextH][nextW]) continue;
		//조건 다 지나왔다면 방문처리해준 후
		visited[nextH][nextW] = true;
		//다음 백트래킹 실행
		Backtracking(nextH, nextW, length + 1);
		//백트래킹 하고 전단계로 돌아오면 방문처리 초기화해줌
		visited[nextH][nextW] = false;
	}

}

void Solution() {
	Backtracking(height - 1, 0, 1);
	cout << ans;
}

int main() {
	Input();
	Solution();

}

문풀후생

다음 칸들만 체크하고 시작칸을 체크 안했더니
시작칸의 방문처리와 시작칸이 T로 처리되어있는지를 확인을 못해서 계속 틀렸다,