9944 NxM 보드 완주하기

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

9944번: NxM 보드 완주하기

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
#define BOARD_SIZE 31
int N, M;//행, 열 크기
int pointCnt = 0;//점의 갯수
char Board[BOARD_SIZE][BOARD_SIZE];//보드판 
int visit[BOARD_SIZE][BOARD_SIZE];//방문확인
//int pointChk = 0;//점의 갯수 체크 갯수
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int cMin = 0x7fffffff;//현재 보드위치의 최소값
int fMin = 0x7fffffff;//마지막 최종 최소값
bool safe(int y, int x) {
	return 0 <= y && y < N && 0 <= x && x < M;
}
void dfs(int y, int x, int dir, int cnt, int pointChk) {// 맵의 y좌표,x좌표, 방향,방향전환수
	if (pointCnt == pointChk) {//전부 다돌았다면
		cMin = cMin > cnt ? cnt : cMin;
		return;
	}
	int ny = y + dy[dir]; int nx = x + dx[dir];
	if (!safe(ny, nx) || visit[ny][nx] == 1 || Board[ny][nx] == '*') {//방향 전환해야하는 경우라면
		for (int d = 0; d < 4; d++) {//방향 바꿔주기
			if (dir == d)continue;
			if (safe(y + dy[d], x + dx[d]) && visit[y + dy[d]][x + dx[d]] == 0 && Board[y + dy[d]][x + dx[d]] == '.') {
				visit[y + dy[d]][x + dx[d]] = 1;
				pointChk++;
				dfs(y + dy[d], x + dx[d], d, cnt + 1, pointChk);//방향 갯수 증가 시키고 넘기기
				pointChk--;
				visit[y + dy[d]][x + dx[d]] = 0;//백트래킹 되면 값 이전 상태로 변경 
			}
		}
	}
	else if (safe(ny, nx) && visit[ny][nx] == 0 & Board[ny][nx] == '.') {
		visit[ny][nx] = 1;
		pointChk++;
		dfs(ny, nx, dir, cnt, pointChk);//그냥 넘겨주기
		pointChk--;
		visit[ny][nx] = 0;//백트래킹 되면 값 이전 상태로 변경 
	}
}
void testPlay() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Board[i][j] == '.') {//시작위치 찾고
				for (int dir = 0; dir < 4; dir++) {//네방향 순서대로 넣기
					visit[i][j] = 1;
					dfs(i, j, dir, 1, 1);
					fMin = fMin > cMin ? cMin : fMin;
					memset(visit, 0, sizeof(visit));
					visit[i][j] = 0;

				}
			}
		}
	}
}
void init() {
	int c = 0;
	while (cin >> N >> M) {
		memset(Board, 0, sizeof(Board));
		scanf("%d %d", &N, &M);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				scanf(" %1c", &Board[i][j]);
				if (Board[i][j] == '.') {//점의 갯수 세는곳
					pointCnt++;
				}
			}
		}
		testPlay();
		c++;
		if (0x7fffffff == fMin)fMin = -1;//못가면 -1
		if (pointCnt == 1)fMin = 0;
		printf("Case %d: %d\n", c, fMin);
		cMin = fMin = 0x7fffffff;
		N = M = pointCnt = 0;//초기화
	}
}
int main(void) {
	init();
	return 0;
}

 이 문제의 포인트는 모든 경우를 다 검색을 하는가 또는 현재 구현한대로 하면 무조건 1부터 계산이 되어 시작되기때문에 조건을 걸어서 걸러줘야했다. 

 

항상 문제를 읽고 나서 조건을 주고 소스를 구현 할때 여러 예제를 생각하면서 구현을 해야겠다. 항상 생각하고 있지만

그래도 이런 실수가 나는 것으로 봐서는 예제조건을 잘 보고 구현할것 그리고 처음에 틀렸다고 나왔었는데 

왜 그렇게 했었는지 모르겠다. 피곤해서 그랬던것 같은데 

이부분에서 visit[i][j]=1 와 visit[i][j]=0 을 해주는 부분을 for 문 밖에다 했었다. 이런 실수 하지 않길 빌겟습니다.