백준 - 1189 컴백홈 (C++)

Pixabay로부터 입수된 Pexels님의 이미지 입니다.

 

---

 

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

1189번: 컴백홈

 

 이번 문제는 맵의 크기를 나타내는 R, C, 이동 거리 K, 그리고 전체 맵이 주어졌을 때 K를 충족하는 경우의 수를 구하는 문제이다. 문제의 예시에서도 알 수 있듯, 이 문제는 가능한 모든 경우를 검사하면 풀 수 있을 것이다. 그리고 문제의 시간 제한이 2초인데다 R과 C의 값이 최대 5이기에 시간초과를 걱정하지 않아도 될 것이다.

 

 가능한 모든 경우를 파악하기 위해서는 깊이 우선 탐색 방식을 이용할 것이다. 깊이 우선 탐색은 간단히 얘기하자면 탐색에 있어 너비보단 깊이를 우선으로 탐색하는 방식이다. 예를 들어, 한 가지 길을 끝까지 가본 후, 다음 경로를 탐색하는 방식이다. 자세한 것은 아래의 링크에서 확인할 수 있다.

 

 이 문제는 상하좌우 4가지 방향으로 진행할 수 있으므로 현재 지점에서 4가지 방향으로 재귀를 이용하면서 나아가면 된다. 만약 현재 지점에서 상하좌우의 다음 지점이 맵의 범위 안에 있으면서, 방문한 적이 없는 곳이면서 'T'가 아닌 경우에 재귀를 통해 그 지점을 방문하는 방식으로 해결할 수 있다.

 

#include <iostream>
#define MAX 6
using namespace std;

int R, C, K;
int startR, startC;
int endR, endC;
int answer = 0;
char givenMap[MAX][MAX];
bool visited[MAX][MAX];
int nr[4] = { 1, -1, 0, 0 };
int nc[4] = { 0, 0, 1, -1 };

bool IsInside(int r, int c)
{
	return 1 <= r && r <= R && 1 <= c && c <= C;
}

void Search(int r, int c, int move)
{
	if (r == endR && c == endC)
	{
		if (move == K)
			++answer;

		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		int nxtR = r + nr[i];
		int nxtC = c + nc[i];

		if (IsInside(nxtR, nxtC))
		{
			if (givenMap[nxtR][nxtC] == '.' && visited[nxtR][nxtC] == false)
			{
				visited[nxtR][nxtC] = true;

				Search(nxtR, nxtC, move + 1);
			
				visited[nxtR][nxtC] = false;
			}
		}
	}
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	std::cin.tie(0);

	cin >> R >> C >> K;

	for (int r = 1; r <= R; ++r)
	{
		for (int c = 1; c <= C; ++c)
			cin >> givenMap[r][c];
	}

	startR = R, startC = 1;
	endR = 1, endC = C;

	visited[startR][startC] = true;

	Search(startR, startC, 1);
	
	cout << answer << endl;

	return 0;
}

---

https://blog.naver.com/ndb796/221230945092

16. 깊이 우선 탐색(DFS)