[백준 2206, 14442, 16933] 벽 부수고 이동하기 1, 2, 3

[백준 2206] 벽 부수고 이동하기 

위에 216ms PQ 사용, 아래 76ms Q 사용

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

2206번: 벽 부수고 이동하기

큐를 사용한 코드는 아래와 같다. 

// Q : 12304kb	76ms
#include <cstdio>
#include <queue>
int N, M, K;
char board[1000 + 2][1000 + 2];
int visited[1000 + 2][1000 + 2][2];		// 0 벽을 안부수고 간다 1 벽을 부수고 간다.

struct _qt
{
	int x, y;
	int cnt;
	int wall;
};


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


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

	std::queue<_qt> Q;
	Q.push({ 1, 1, 1, 0 });
	visited[1][1][0] = 1;

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

		if (data.x == N && data.y == M) return data.cnt;


		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 > M) continue;
			if (visited[nx][ny][data.wall]) continue;

			// 벽을 만나지 않은 경우 
			if (board[nx][ny] == '0') {
				Q.push({ nx, ny, data.cnt + 1 , data.wall });
				visited[nx][ny][data.wall] = 1;
			}
			// 벽을 만났는데 아직 벽 한개도 안부순 경우 
			else if (board[nx][ny] == '1' && data.wall < 1) {
				if (visited[nx][ny][data.wall + 1]) continue;
				Q.push({ nx, ny, data.cnt + 1, data.wall + 1 });
				visited[nx][ny][data.wall + 1] = 1;
			}
			else continue;
		}
		
	}
	return -1;
}



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

1. 벽을 부수지 않고 지나갔는지(0), 벽을 부수고 지나갔는지(1) 를 확인하기 위해 3차원 배열을 사용한다. 

2. 벽을 부수지 않고 지나갔을 경우와, 부수고 지나갔을 경우 해당 칸에 도달기 위한 최단 경로가 달라질 수 있다. 따라서 메모이제이션 + visited 배열로 "해당 칸에 도달하기 까지의 경로"를 비교해준다.

3. PQ를 사용할 수도 있지만, 어차피 이동하는데 모든 cost가 1로 동일하기 때문에 시간이 더 오래걸릴 뿐이다. 

 

우선순위 큐를 사용한 코드는 아래와 같다.

// PQ: 16208kb	216ms
#include <cstdio>
#include <queue>
#include <algorithm>
int R, C;
char board[1000 + 2][1000 + 2];
int visited[1000 + 2][1000 + 2][2];	// 벽을 부수고 갔는지 안부수고 갔는지 

struct _st
{
	int x, y;
	int wall;
	int dist;
};

struct COMP
{
	bool operator() (const _st &a, const _st &b) {
		return a.dist > b.dist;
	}

};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;


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

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

	// init
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			visited[i][j][0] = 0x7fffffff;
			visited[i][j][1] = 0x7fffffff;
		}
	}

	PQ.push({ 1, 1, 0, 1});
	visited[1][1][0] = 1;	// 시작하는 칸 포함해서 센다 

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.x == R && data.y == C) return data.dist;
		
		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 > R || ny < 1 || ny > C) continue;
			if (visited[nx][ny][data.wall] <= data.dist + 1) continue;

			if (board[nx][ny] == '1' && data.wall == 0) {	// 벽을 만났고 지금까지 0개 뿌시고 왔을 때 
				if (visited[nx][ny][data.wall + 1] <= data.dist + 1) continue;
				PQ.push({ nx, ny, data.wall + 1, data.dist + 1 });
				visited[nx][ny][data.wall + 1] = data.dist + 1;
			}
			else if (board[nx][ny] == '0') {	// 벽을 안만났을 때 
				PQ.push({ nx, ny, data.wall, data.dist + 1 });
				visited[nx][ny][data.wall] = data.dist + 1;
			}
		}
	}
	return -1;
}


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

---

[14442 벽 부수고 이동하기 2]

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

14442번: 벽 부수고 이동하기 2

PQ를 사용할 필요 없다.

벽을 몇개 부수었는지 여부와, 해당 칸 까지 도달하기 위해 이동한 경로를 저장한 3차원 방문배열 비교하면 큐로 충분하다. 

코드는 아래와 같다. 

#include <cstdio>
#include <queue>
int R, C, K;
char board[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
	int wall;
	int dist;
};

std::queue<_st> Q;
int visited[1000 + 2][1000 + 2][10 + 1];	// 0벽을 부수지 않거나 1~10개 까지 부수고 이동할 수 있다.

void input()
{
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}
}

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

	// init
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			for (int k = 0; k <= K; k++) {
				visited[i][j][k] = 0x7fffffff;
			}
		}
	}

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

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

		if (data.x == R && data.y == C) return data.dist;	// 큐에 먼저 들어간 애가 먼저 나온다. 
															// 가장 먼제 (R, C)를 만나는 큐의 원소가 가장 먼저 해당 칸에 도달한 것이다. 

		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 > R || ny < 1 || ny > C) continue;
			if (visited[nx][ny][data.wall] <= data.dist + 1) continue;

			if (board[nx][ny] == '1' && data.wall < K) {
				if (visited[nx][ny][data.wall + 1] <= data.dist + 1) continue;
				Q.push({ nx, ny, data.wall + 1, data.dist + 1 });
				visited[nx][ny][data.wall + 1] = data.dist + 1;
			}
			else if (board[nx][ny] == '0') {
				Q.push({ nx ,ny, data.wall, data.dist + 1 });
				visited[nx][ny][data.wall] = data.dist + 1;
			}
			else continue;
		}
	}
	return -1;
}





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

---

[백준 16933] 벽 부수고 이동하기 3

백준 메모리 내가 다 잡아먹음..

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

16933번: 벽 부수고 이동하기 3

위의 문제들과 동일하게 접근하면 된다. 

주의할 점은

1. 한 번 이동하면 낮과 밤이 바뀌고

2. 이동하지 않고 같은 칸에 머물러 있을 수 있으며, 이 경우에도 방문한 칸의 개수가 한 칸 더 늘어나는 것으로 간주한다. 또한 이동하지 않는 경우에도 낮과 밤이 바뀐다.

#include <cstdio>
#include <queue>
int R, C, K;
char board[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
	int wall;
	int dist;
	int is_day;	// 0이면 저녁 1이면 낮
};

std::queue<_st> Q;
int visited[1000 + 2][1000 + 2][10 + 1][2];	// 0~K개까지 벽을 부술 수 있고, 현재 칸에 낮에 도달했는지 밤에 도달했는지 


void input()
{
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}
}

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

	// init
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			for (int k = 0; k <= K; k++) {
				visited[i][j][k][0] = 0x7fffffff;
				visited[i][j][k][1] = 0x7fffffff;
			}
		}
	}

	Q.push({ 1, 1, 0, 1, 1 });	// 가장 처음 이동할 때는 낮이다 
	visited[1][1][0][1] = 1;

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

		if (data.x == R && data.y == C) return data.dist;

		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 > R || ny < 1 || ny > C) continue;
			// 한 번 이동(data.dist + 1)할 때 마다 낮과 밤이 바뀐다(1 - data.is_day)
			if (visited[nx][ny][data.wall][1 - data.is_day] <= data.dist + 1) continue; 

			if (board[nx][ny] == '1' && data.wall < K && data.is_day == 1) {	// 벽을 만났고, K개 미만으로 벽을 부수었고, 낮이면
				if (visited[nx][ny][data.wall + 1][1 - data.is_day] <= data.dist + 1) continue;
				Q.push({ nx, ny, data.wall + 1, data.dist + 1, 1 - data.is_day });
				visited[nx][ny][data.wall + 1][1 - data.is_day] = data.dist + 1;
			}
			else if (board[nx][ny] == '0') {
				Q.push({ nx, ny, data.wall, data.dist + 1, 1 - data.is_day });
				visited[nx][ny][data.wall][1 - data.is_day] = data.dist + 1;
			}
			else continue;
		}
		// 이동하지 않고 같은 칸에 머물러 있는 경우도 가능하다. 
		if (visited[data.x][data.y][data.wall][1 - data.is_day] <= data.dist + 1) continue;
		Q.push({ data.x, data.y, data.wall, data.dist + 1, 1 - data.is_day });
		visited[data.x][data.y][data.wall][1 - data.is_day] = data.dist + 1;
		
	}
	return -1;
}


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