백준 1189번 컴백홈 dfs(C++)

문제

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

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

using namespace std;

int r,c,k;
int cnt =0;

// void	print_map(vector<vector<int>> arr)
// {
// 	for (int i=0;i < r;i++)
// 	{
// 		for (int j =0;j < c;j++)
// 		{
// 			cout << arr[i][j] << " ";
// 		}
// 		cout << "\n";
// 	}
// }

void dfs(int x,int y,vector<vector<int>> arr,int depth)
{
	// cout << depth<< "\n";
	// print_map(arr);
	if (x == c-1 && y == 0)
	{
		if (depth == k)
			cnt++;
		return;
	}
	else if (depth == k)
		return ;
	for (int i=0;i <4;i++)
	{
		if (x + dx[i] < 0 || x + dx[i] >= c || y + dy[i] <0 || y + dy[i] >= r)
			continue;
		if (arr[y + dy[i]][x + dx[i]] == 0)
		{
			arr[y + dy[i]][x + dx[i]] = 1;
			dfs(x + dx[i],y + dy[i],arr,depth+1);
			arr[y + dy[i]][x + dx[i]] = 0;
		}
	}
}
int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> r >> c >> k;
	vector arr(r,vector<int>(c,0));
	for (int i=0;i < r;i++)
	{
		string s;
		cin >> s;
		for (int j=0; j<c;j++)
		{
			if (s[j] == '.')
				arr[i][j] = 0;
			else if (s[j] == 'T')
				arr[i][j] = -1;
		}
	}
	arr[r-1][0] =1;
	dfs(0,r -1,arr,1);
	cout << cnt;
}

문제 풀이의 흐름

• 입력을 쭉 받는다.

• 갈 수 없는 곳에는 -1을 넣어준다.

• 시작 하는부분을 1로 칠한다.

• dfs를 시작한다.

• 끝까지 도달한 경우 깊이가 원하는 값과 같다면 결과에 1을 더해준다.

• 만약 깊이가 원하는 것보다 깊다면 멈춘다.

• 이 과정을 계속 해서 진행한다.

주의 할 점

한번 갔다 온 경우 다시 0으로 초기화 해줄 필요가 있다.

왜냐면 다른 경로로 다시 그 길로 들어올 수 있기 때문이다.

반성 및 고찰

이 문제는 나 스스로 좀 부끄럽다.

인덱스를 j를 넣어야하는 부분에 i를 넣어서 몇시간을 헤맨건지 모르겠다.

결국 직접 맵을 찍어보고 나서야 이 실수를 알게 되었는데 조금 더 집중할 필요가 있어보인다..

Uploaded by N2T