[BOJ] 백준 2206번 벽 부수고 이동하기 c++

BOJ 문제 링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

N * M 크기의 맵이 있다. 맵에서 벽은 1, 벽이 없는 곳은 0으로 표현된다.

(1,1)에서 (N,M) 위치까지 상하좌우로 한칸씩 이동면서 최단경로를 구하는 문제이다.

이때 벽을 부수고 이동하는 경우 경로가 더 짧아진다면, 벽을 한 개 까지 부수고 이동하여 된다.

 

bfs를 이용하면 문제를 해결할 수 있다. 이때 이미 지나온 곳을 다시 지나는것을 막기위해 discover배열을 둔다.

단, 벽을 부술 수 있는 상태인지 이미 벽을 부순 상태인지에 따라 이동할 수 있는 경로가 달라지므로 discover를 이차원이 아닌 3차원 배열로 한다.

 

	#include<iostream>
	#include<queue>
	using namespace std;
	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { -1,1,0,0 };
	char adj[1000][1000];
	bool discover[1000][1000][2] = { 0, };
	struct state {
	int cost, x, y;
	bool power;
	state(int cost, int x, int y, bool power) {
	this->cost = cost;
	this->x = x;
	this->y = y;
	this->power = power;
	}
	};
	// 범위에서 벗어나는 좌표인지 확인
	bool boundValidation(int x, int y, int desX, int desY) {
	if (x<0 || x>desX)
	return false;
	if (y<0 || y>desY)
	return false;
	return true;
	}
	// (desX, desY)에 도착할때의 비용 return
	int solve(int desX, int desY) {
	queue<state> q;
	q.push(state(0, 0, 0, true));
	discover[0][0][true] = true;
	int ret = 1;
	while (!q.empty()) {
	int cost = q.front().cost;
	int x = q.front().x;
	int y = q.front().y;
	bool power = q.front().power;
	q.pop();
	// 도착했다면 거리 return
	if (x == desX && y == desY) {
	return cost + 1;
	}
	// 현재 위치에서 상하좌우 검사
	for (int i = 0; i < 4; i++) {
	int nextX = x + dx[i];
	int nextY = y + dy[i];
	int nextCost = cost + 1;
	bool nextPower = power;
	// 범위에 벗어나지 않고, 벽이 아니거나 벽을 부술 수 있고, 방문한적이 없으면 방문예정
	if (boundValidation(nextX, nextY, desX, desY) &&
	(adj[nextY][nextX] == '0' || nextPower) && (discover[nextY][nextX][nextPower] == false)) {
	// 벽을 부수고 온거면 더 이상 벽을 못부숨
	if (adj[nextY][nextX] == '1')
	nextPower = false;
	// 방문예정 목록에 추가 해놓음
	q.push(state(nextCost, nextX, nextY, nextPower));
	discover[nextY][nextX][nextPower] = true;
	}
	}
	}
	return -1;
	}
	int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
	cin >> adj[i][j];
	cout << solve(m - 1, n - 1);
	}

view raw [BOJ] 백준 2206번 벽 부수고 이동하기.cpp hosted with ❤ by GitHub

 

코드원본: https://github.com/sbl133/BOJ/blob/main/%232206.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!