[C++] 백준 벽 부수고 이동하기 1, 2, 3, 4

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

2206번: 벽 부수고 이동하기

벽 부수고 이동하기 1번부터...

 

사용한 알고리즘: BFS (BFS를 사용했으므로 벽을 뚫고 가는 경우가 더 빠른지, 벽을 뚫고 가지 않는 경우가 더 빠른지 비교해 주는 IF문 등이 필요 없음을 이해하는 것이 중요하다고 생각한다)

또한, dp에서 0, 1 로 벽을 뚫었을 경우와 뚫지 않았을 경우를 나눠주는 이유는

해당 문제를 bfs로 풀려면 답에 영향을 주는 모든 상태를 나타내야 하므로

벽을 뚫음/뚫지않음 을 꼭 표시해줘야 한다

벽을 이미 뚫었을 경우/아닌 경우 로 나누어서 봐줬는데,

(ni, nj)가 벽인경우, 벽이 아닌 경우로 나누어줘도 아무 상관없다

 

(이 문제를 bfs로 푸는 이유는 최단거리 문제이기 때문인데,

bfs로 품으로써 벽을 뚫는 경우가 더 빠른지/벽을 뚫지 않고 가는 경우가 더 빠른지

값을 비교하면서 탐색할 필요가 없어진다

애초에 bfs는 한 걸음씩 이동할 때마다 그 이동이 가장 최소가 되기 때문이다

 

그래서 처음에는 문제를 보고 "벽을 뚫는 경우가 더 빠른지/벽을 뚫지 않고 가는 경우가 더 빠른지"

이런 걸 봐줄까 하고 막연하게 생각했었는데

음 이문제를 DFS로 푼다면 그렇게 해도 될 거 같긴 하다

아무튼  BFS를 사용했으므로 벽을 뚫고 가는 경우가 더 빠른지, 벽을 뚫고 가지 않는 경우가 더 빠른지 비교해 주는 if문 등이 필요 없음을 이해하는 것이 중요하다고 생각한다

 

또한, dp에서 0, 1로 벽을 뚫었을 경우와 뚫지 않았을 경우를 나눠주는 이유는

해당 문제를 bfs로 풀려면 답에 영향을 주는 모든 상태를 나타내야 하므로

벽을 뚫음/뚫지 않음 을 꼭 표시해줘야 한다)

 

 

아래 코드에서

dp가 visit의 역할도 해주고 cnt도 세준다

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct info {
	int i, j;
	bool b;
};

int N, M;
bool map[1000][1000];
int dp[1000][1000][2];
int didj[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void bfs() {
	queue<info> q;
	q.push({ 0, 0, false });
	dp[0][0][0] = 1;

	while (!q.empty()) {
		int ci = q.front().i;
		int cj = q.front().j;
		bool broken = q.front().b;
		q.pop();

		if (ci == N - 1 && cj == M - 1) {
			return;
		}

		for (int k = 0; k < 4; k++) {
			int ni = ci + didj[k][0];
			int nj = cj + didj[k][1];
			if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
            if (dp[ni][nj][broken] != 0) continue;
			
			//이미 뚫고 옴
			if (broken) {
				//벽이면 스킵
				if (map[ni][nj]) continue;
				dp[ni][nj][1] = dp[ci][cj][1] + 1;
				q.push({ni, nj, true});
			}
			else {
				//벽이면 뚫어보기
				if (map[ni][nj]) {
					dp[ni][nj][1] = dp[ci][cj][0] + 1;
					q.push({ ni, nj, true });
				}
				else {
					//벽 아니면 그냥 계속
					dp[ni][nj][0] = dp[ci][cj][0] + 1;
					q.push({ ni, nj, false });
				}
			}
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	char row[1001];
	for (int i = 0; i < N; i++) {
		scanf("%s", row);
		for (int j = 0; j < M; j++) {
			map[i][j] = row[j] - '0';
		}
	}
	bfs();
	
	//도달 불가능
	if (!dp[N - 1][M - 1][0] && !dp[N - 1][M - 1][1]) printf("-1");
	else {
		if(!dp[N - 1][M - 1][0]) printf("%d", dp[N - 1][M - 1][1]);
		else if(!dp[N - 1][M - 1][1]) printf("%d", dp[N - 1][M - 1][0]);
		else printf("%d", min(dp[N - 1][M - 1][0], dp[N - 1][M - 1][1]));
	}
}

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

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

벽 부수고 이동하기 2

 

1과 완전히 똑같은 문제이고, 부술 수 있는 벽의 개수가 1개에서 K개로 늘어난 차이밖에 없다

K가 다행히 10까지여서 3차원 배열로 표현할 수 있는 문제인데,

K가 훨씬 더 커지면 다른 방법을 생각해봐야 할 듯

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct info {
	int i, j;
	int bc;
};

int N, M, K;
bool map[1000][1000];
int dp[1000][1000][11];//cnt 및 visit
int didj[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void bfs() {
	queue<info> q;
	q.push({ 0, 0, 0 });
	dp[0][0][0] = 1;

	while (!q.empty()) {
		int ci = q.front().i;
		int cj = q.front().j;
		int broken_cnt = q.front().bc;
		q.pop();

		if (ci == N - 1 && cj == M - 1) {
			return;
		}

		for (int k = 0; k < 4; k++) {
			int ni = ci + didj[k][0];
			int nj = cj + didj[k][1];
			if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
			if (dp[ni][nj][broken_cnt]) continue;
			
			//벽일 경우
			if (map[ni][nj]) {
				//뚫고 가보기 음 두번째 조건은 의미 없으려나
				if (broken_cnt == K || dp[ni][nj][broken_cnt + 1]) continue;
				dp[ni][nj][broken_cnt + 1] = dp[ci][cj][broken_cnt] + 1;
				q.push({ ni, nj, broken_cnt + 1 });
			}
			else {
				//그냥 ㄱㄱ
				dp[ni][nj][broken_cnt] = dp[ci][cj][broken_cnt] + 1;
				q.push({ni, nj, broken_cnt});
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &K);
	char row[1001];
	for (int i = 0; i < N; i++) {
		scanf("%s", row);
		for (int j = 0; j < M; j++) {
			map[i][j] = row[j] - '0';
		}
	}
	bfs();
	
	bool unreachable = true;
	for (int i = 0; i <= K; i++) {
		if (dp[N - 1][M - 1][i] != 0) {
			unreachable = false;
			break;
		}
	}

	//도달 불가능
	if (unreachable) printf("-1");
	else {
		int ans = 2000000;
		for (int i = 0; i <= K; i++) {
			if (dp[N - 1][M - 1][i] == 0) continue;
			ans = min(ans, dp[N - 1][M - 1][i]);
		}
		printf("%d", ans);
	}
}

 

 

벽 부수고 이동하기 3

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

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

 

이 문제에서 가장 중요한 부분은

언제 낮이 바뀔 때까지 그 자리에서 가만히 있어야 되냐 인 것 같다

벽인 경우, 못 뚫었을 때 한번 기다리고 나서 뚫을 수 있기 때문에 기다리는 것이 의미가 있지만

벽이 아닌 경우 이동하지 않고 가만히 있는 것은 의미가 없다

 

또한, 지난 벽부이 1,2에서는 dp를 visit 및 cnt로 세주었는데,

이 문제에서도 그렇게 해주면 예제 4에서 오류가 난다

그 이유는, cnt를 세줄 때 (ci, cj)의 dp값을 가져오는데,

한 자리에 가만히 있는다고 dp[ci][cj]값을 ++ 해주게 되면

cnt를 세줄 때 dp값을 가져오는 과정에서 최솟값이 아니게 되어버린다

 

즉 cicj에 가만히 있는 행동이 다른 경로로 이동했을 때의 cnt값에 영향을 주게 되므로

cnt값은 dp에 저장해서 가져오는 방식이 아닌 큐에 넣는 방식으로 해줘야 한다

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct info {
	int i, j, bc, cnt;
	bool in;
};

int N, M, K;
bool map[1000][1000];
bool dp[1000][1000][11];//visit
int ans[11];
int didj[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void bfs() {
	queue<info> q;
	q.push({ 0, 0, 0, 1, true });
	dp[0][0][0] = true;

	while (!q.empty()) {
		int ci = q.front().i;
		int cj = q.front().j;
		int broken_cnt = q.front().bc;
		int cur_cnt = q.front().cnt;
		bool is_nat = q.front().in;
		q.pop();

		if (ci == N - 1 && cj == M - 1) {
			ans[broken_cnt] = cur_cnt;
			return;
		}

		for (int k = 0; k < 4; k++) {
			int ni = ci + didj[k][0];
			int nj = cj + didj[k][1];
			if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
			if (dp[ni][nj][broken_cnt]) continue;
			
			//벽임
			if (map[ni][nj]) {
				//음 두번째 조건은 의미 없으려나
				if (broken_cnt == K || dp[ni][nj][broken_cnt + 1]) continue;
				//낮이면 뚫기
				if (is_nat) {
					dp[ni][nj][broken_cnt + 1] = true;
					q.push({ ni, nj, broken_cnt + 1, cur_cnt + 1, !is_nat });
				}
				else {
					//가만히 있기
					q.push({ ci, cj, broken_cnt, cur_cnt + 1, !is_nat });
				}
			}
			else {
				//안뚫고 ㄱㄱ
				dp[ni][nj][broken_cnt] = true;
				q.push({ ni, nj, broken_cnt, cur_cnt + 1, !is_nat });
				//벽이 아닌데 가만히 있는 경우는.. 고려 안해도 될거같음
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &K);
	char row[1001];
	for (int i = 0; i < N; i++) {
		scanf("%s", row);
		for (int j = 0; j < M; j++) {
			map[i][j] = row[j] - '0';
		}
	}
	bfs();
	
	bool unreachable = true;
	for (int i = 0; i <= K; i++) {
		if (ans[i] != 0) {
			unreachable = false;
			break;
		}
	}

	//도달 불가능
	if (unreachable) printf("-1");
	else {
		int min_ans = 2000000;
		for (int i = 0; i <= K; i++) {
			if (ans[i] == 0) continue;
			min_ans = min(min_ans, ans[i]);
		}
		printf("%d", min_ans);
	}
}