[Algorithm][C++] BOJ 16954 움직이는 미로 탈출

url: https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

풀이 핵심

1. 방문 여부 체크 하지 않는다 (중복 해서 방문 할 수 있으므로)

2. 다음 2가지 조건 중 하나라도 만족하면 가장 오른쪽 윗 칸에 도달할 수 있다고 판단한다

• 현재 위치가 가장 오른쪽 윗 칸이라면
• 남아있는 벽이 없다면

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define N (8)

int sr = 7, sc = 0, er = 0, ec = 7;
int ans;

struct BOARD {
	char map[N + 1][N + 1];
	int r, c;
	int wall_cnt;

	void move_wall() {
		int tmp_cnt = 0;
		char temp[N + 1][N + 1] = { "........", };
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < N; j++) {
				temp[i][j] = map[i - 1][j];
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = temp[i][j];
				if (temp[i][j] == '#') tmp_cnt++;
			}
		}
		wall_cnt = tmp_cnt;
	}
};

void dfs(BOARD cur) {
	if ((cur.r == er && cur.c == ec) || !cur.wall_cnt) {
		ans = 1;
		return;
	}
	const int dr[] = { 1,-1,0,0,1,1,-1,-1,0 };
	const int dc[] = { 0,0,1,-1,1,-1,1,-1,0 };
	for (int dir = 0; dir < 9; dir++) {
		BOARD next = cur;
		next.move_wall();
		int nr = cur.r + dr[dir];
		int nc = cur.c + dc[dir];
		if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
		if (cur.map[nr][nc] == '#' || next.map[nr][nc] == '#') continue;
		next.r = nr, next.c = nc;
		dfs(next);
	}
}

int main() {
	BOARD board;
	board.r = sr, board.c = sc;
	board.wall_cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf(" %c", &board.map[i][j]);
			if (board.map[i][j] == '#') board.wall_cnt++;
		}
	}
	dfs(board);
	printf("%d", ans);
	return 0;
}