[백준 2665] 미로만들기

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

2665번: 미로만들기

#include <cstdio>
#include <queue>
#include <algorithm>
int N;
char room[50 + 2][50 + 2];
int chk[50 + 2][50 + 2];	// 검은방 -> 흰방 바꾼 개수 

struct _st
{
	int x;
	int y;
	int flag;	// 검은방-> 흰방 몇개 바꾸었는지
};

std::queue<_st> Q;

void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%s", &room[i][1]);
	}
}

void init()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			chk[i][j] = 0x7fffffff;
		}
	}
}


int BFS()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	// chk배열 초기화
	init();

	Q.push({ 1, 1, 0 });	// (1, 1) 방을 0개 바꿈 
	chk[1][1] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;	// 영역을 벗어났다면 스루
			if (chk[nx][ny] <= data.flag) continue;

			if (room[nx][ny] == '0') {	// 검은방을 만났다면 
				int nflag = data.flag + 1;
				if (chk[nx][ny] <= nflag) continue;
				chk[nx][ny] = nflag;
				Q.push({ nx, ny, nflag });
			}
			else {
				chk[nx][ny] = data.flag;
				Q.push({ nx, ny, data.flag });
			}
		}
	}
	return chk[N][N];
}



int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

비용의 관점에서 BFS를 돌리는 문제이다. 

처음에 "벽 부수고 이동하기 2" 문제랑 동일하게 접근하는 문제인줄 알고 좀 헤맸다. 나름대로 정리한 차이점은 다음과 같다.

 

<벽 부수고 이동하기 2>

(1, 1)에서 (N, N)까지 벽을 K개 만큼만 부수면서 갈 수 있는 "최단 경로"를 구하는 문제이다. 따라서 "부순 벽의 개수가 0일때 부터 K일 때 까지의 최단 경로를 3차원 체크배열에 표시"해주었어야 했다. 

또한 한 칸을 이동하는데 필요한 cost가 모두 동일하므로, 큐에서 방금 pop된 좌표가 (N, N)이라면 더이상 탐색할 필요 없이 바로 data.cnt를 리턴해준다. (이것이 optimal choice이기 때문)

AC코드 : https://kimsouce.tistory.com/274

 

<미로 만들기>

(1, 1)에서 (N, N)까지 도달하는데 검은방에서 흰방으로 바꾸어야할 "최소의 수"를 구하는 문제이다. 따라서 "각 칸에 도달할 때 까지 바꾼 방의 최소 횟수를 2차원 체크배열에 표시"해주었어야 했다. 

또한 해당 칸에 도달하는데 어떤 경로를 선택하느냐에 따라 검은방 -> 흰방으로 바꾼 횟수가 달라질 수 있으므로, 큐의 원소가 모두 pop 될 때 까지 탐색을 진행해야 한다. 그 다음 while 루프를 빠져나왔을 때 chk[N][N]를 리턴해준다. ((N, N)까지 도달할 수 있는 모든 경우의 수를 탐색해 보아야 하기 때문)

 

 

// BFS( ) 함수

위의 설명을 토대로, chk 배열에는 해당 칸을 방문 했는지 안했는지의 여부를 기록하는 것이 아니라, "해당 칸에 도달할 때 까지 몇 개의 방을 변경했는지" 에 대한 정보를 담아야 한다. 

따라서 큐에서 pop된 좌표의 data.flag(좌표 (data.x, data.y)까지 도달하는데 변경한 방의 개수)가  chk[nx][ny](새로 이동할 좌표(nx, ny)까지 도달하는데 변경한 최소 방의 개수)보다 크거나 같으면, 더이상 탐색을 진행하지 않아도 된다. 어차피 optimal choice의 후보가 될 수 없기 때문이다. 

 

그리고 새롭게 이동할 칸이 검은 방이라면 방 변경 횟수를 1 증가시키고(nflag = data.flag  + 1) , 만약 해당 값이 chk배열에 저장된 좌표 (nx, ny)까지 도달하는데 최소 변경 횟수와 비교하여 크거나 같으면 더 이상 탐색을 진행하지 않는다. 그렇지 않으면 chk 배열을 갱신하고 큐에 삽입한다. 

 

새롭게 이동할 칸이 흰 방이라면 방의 변경이 필요하지 않으므로 chk 배열에 변경 횟수를 그대로 저장한다(chk[nx][ny] = data.flag). 그리고 해당 정보를 큐에 삽입한다. 

---

++22.11.07 다시 풀어보았지만 더 비효율적인 코드 탄생... 

벽 부수고 이동하기 처럼 풀어도 된다. 그러나 방문배열에 바꾼 방의 개수 표시해주는게 훨씬 효율적일듯..

3차원 방문 배열 썼다.  

#include <cstdio> 
#include <queue>
#include <cstring>
int N;
char board[50 + 2][50 + 2];
int ans = 0x7fffffff;

struct _st
{
	int x, y;
	int change;
	int move;
};
std::queue<_st> Q;
int visited[50 + 2][50 + 2][2500 + 2];	// 최악 : 시작 끝방 빼고 50 * 50 맵 싹 다 검은방인 경우 


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", &board[i]);
	}
}


void BFS()
{
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init visit
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int c = 0; c <= N * N; c++) {
				visited[i][j][c] = 0x7fffffff;
			}
		}
	}

	Q.push({ 0, 0, 0, 0 });
	visited[0][0][0] = 0;
	

	while (!Q.empty()) {
		_st data = Q.front();
		//printf("%d %d %c\n", data.x, data.y, board[data.x][data.y]);
		Q.pop();

		if (data.x == N - 1 && data.y == N - 1) {
			if (ans > data.change) ans = data.change;
			continue;
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny][data.change] <= data.move + 1) continue;

			// 흰 방
			if (board[nx][ny] == '1') {
				Q.push({ nx, ny, data.change, data.move + 1 });
				visited[nx][ny][data.change] = data.move + 1;
			}
			// 검은 방 
			else if (board[nx][ny] == '0') {
				if (visited[nx][ny][data.change + 1] <= data.move + 1) continue;
				Q.push({ nx, ny, data.change + 1, data.move + 1 });
				visited[nx][ny][data.change + 1] = data.move + 1;
			}
		}
	}
}



int main()
{
	input();
	BFS();
	printf("%d\n", ans);
	return 0;
}