[소프티어] 순서대로 방문하기

문제

https://softeer.ai/practice/info.do?idx=1&eid=2050&sw_prbl_sbms_sn=266553

접근 방법

주어진 m개 위치를 순서대로 방문하는 개수를 구하는 문제이다.
완전탐색 + 백트래킹으로
다음 목적지 idx, 현재 위치 y, x를 매개변수로
방문 후 재귀함수 호출, 방문 해제를 하면서
모든 경우의 수를 구했다.

풀이

#include <iostream>
#include <vector>

using namespace std;

int map[5][5]; // 지도 배열
bool visited[5][5]; // 지도 배열
vector<pair<int, int>> goals; // 목적지 벡터
int n, m;
int result = 0;

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

void FastIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void Input()
{
	// 백트래킹
	cin >> n >> m;

	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cin >> map[i][j];
		}
	}

	int x, y; 

	for(int i=0; i<m; i++)
	{
		cin >> y >> x;
		goals.push_back({y, x});
	}
}

void Backtracking(int idx, int y, int x)
{
	// 목적지에 도착했을 경우 
	if (goals[idx].first == y && goals[idx].second == x)
	{
		if (idx == m-1)
		{
			result++; // 개수 증가 
			return;
		}

		Backtracking(idx+1, y, x);
	}

	for(int i=0; i<4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		// 범위 초과했으면 패스 
		if (ny <= 0 || ny > n || nx <= 0 || nx > n)
			continue;
		// 방문했거나 벽이라면 패스 
		if (visited[ny][nx] || map[ny][nx])
			continue;

		visited[ny][nx] = true; // 방문 
		Backtracking(idx, ny, nx);
		visited[ny][nx] = false; // 방문 해제
	}
}

void Solve()
{
	// 시작점 지정
	int y = goals[0].first;
	int x = goals[0].second;
	visited[y][x] = true;
	Backtracking(1, y, x);

	cout << result;
}

int main(int argc, char** argv)
{
	FastIO();
	Input();
	Solve();

	return 0;
}

정리

얼핏 보고 BFS인줄 알았으나 완전탐색이었다..
백트래킹의 정석같은 문제

참고

https://velog.io/@yeguu037/%EC%86%8C%ED%94%84%ED%8B%B0%EC%96%B4-%EC%88%9C%EC%84%9C%EB%8C%80%EB%A1%9C-%EB%B0%A9%EB%AC%B8%ED%95%98%EA%B8%B0-JavaScript-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9