[C++]백준 9944번 : NxM 보드 완주하기

www.acmicpc.net/problem/9944

9944번: NxM 보드 완주하기

1. 접근

공이 방향을 전환하는 분기가 있고, 각 분기로 나누어진 경우마다 모든 map을 탐색할 수 있는지를 알아야하기 때문에 dfs를 생각했다.

모든 맵을 탐색했는지 확인하기 위해서

1) 더 이상 못움직이는 경우 모든 맵을 탐색했는지 반복문으로 확인하여 결과 도출

2) map을 입력 받을 때 탐색할 수 있는 공간의 개수를 따로 저장해서 활용하여 결과 도출

 

두 가지를 생각했는데 2번째 방식이 가독성, 시간 면에서 조금 더 낫다고 생각해서 2번째 방식을 선택했다.

 

 

2. 풀이과정

재귀마다 4가지 방향을 본 뒤 도달할 수 있는 방향까지 check하고 다음 재귀, 재귀 후 uncheck하는 방식으로 구현했다.

3번이나 틀리고나서야 출력에 띄어쓰기를 안해서 틀렸다는 걸 알았다..

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>

using namespace std;

int T, N, M, K;
char map[31][31];
bool chk[31][31] = { false, };
pair<int, int> dir[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

int ans;

void dfs(int y, int x, int cnt, int k){
	// 조금이나마 시간 줄이기
	if (ans < cnt)
		return;
	
    // 모두 탐색한 경우에 ans 갱신
	if (k == 0){
		if (ans > cnt)
			ans = cnt;
		return;
	}


	for (int i = 0; i < 4; i++){
		int ny = y + dir[i].first, nx = x + dir[i].second;
		int nk = k;

		// 현재 방향으로 탐색할 수 있을 때 까지 탐색
		while (ny >= 0 && ny < N && nx >= 0 && nx < M && map[ny][nx] == '.' && !chk[ny][nx]){
			chk[ny][nx] = true;
			nk--;
			ny += dir[i].first;
			nx += dir[i].second;
		}

		ny -= dir[i].first;
		nx -= dir[i].second;

		if (ny != y || nx != x){

			dfs(ny, nx, cnt + 1, nk);
			
            
            // 이번 반복문에서 탐색한 영역 되돌리기
			while (ny != y || nx != x){
				chk[ny][nx] = false;
				ny -= dir[i].first;
				nx -= dir[i].second;
			}
		}
	}

	return;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	T = 0;
			
	while (cin >> N >> M){
		// init
        ans = INT_MAX;
		K = 0;
		memset(chk, false, sizeof(chk));
		
		
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++){
				cin >> map[i][j];
				if (map[i][j] == '.')
					K++; // 탐색되어야할 공간의 수
			}

				
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (map[i][j] == '.'){
					chk[i][j] = true;
					dfs(i, j, 0, K - 1); // 재귀 시작
					chk[i][j] = false;
				}
					
		if (ans == INT_MAX)
			cout << "Case " << ++T << ": " << -1 << "\n";
		else
			cout << "Case " << ++T << ": " << ans << "\n";
	}

	return 0;
}