[BOJ] 2206 : 벽 부수고 이동하기

Drakk·2021년 7월 20일

알고리즘 문제풀이

목록 보기

7/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

🧺출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

🔋예제 입출력

🔮예제 입력1
6 4
0100
1110
1000
0000
0111
0000

🔮예제 출력1
15

🔮예제 입력2
4 4
0111
1111
1111
1110

🔮예제 출력2
-1

💉문제 분석

🔋분류

BFS

🔋난이도

골드IV

💉문제 풀이

🔋해법

이 문제는 일반적인 bfs문제입니다.
단, 비용을 계산하는 배열(visit)은 3차원으로 했습니다.
이유는 현재 벽을 부술수있는지 확인하기 위함입니다.
bfs함수의 3번째 인자로 lmx를 1로 줬는데, 이거는 최대로 부술수있는 벽의 갯수입니다.
문제에서는 총 1개의 벽만 부술수있다고했으니 1로 준겁니다.

bfs조건문에서 adj[ny][nx]가 1일때는 b > 0라고했는데, 이거는 부술수있는지 여부를 확인하는겁니다. b가 0이면 더이상 부술수없다는 뜻이죠.
반면에, adj[ny][nx]가 0일때는 좀 다릅니다. 그냥 방문여부만 확인해주면됩니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 1001;
constexpr int INF = 987654321;

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };

int adj[MAX][MAX];
int visit[MAX][MAX][3];

int bfs(int N, int M, int lmx){
	std::queue<std::pair<std::pair<int, int>, int>>q;
	q.push({ { 0, 0 }, lmx });
	visit[0][0][lmx] = 1;
	
	while(!q.empty()){
		int y = q.front().first.first;
		int x = q.front().first.second;
		int b = q.front().second;
		q.pop();
		
		if(y == N - 1 && x == M - 1) return visit[y][x][b];
		
		for(int i=0;i<4;++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(nx >= 0 && ny >= 0 && nx < M && ny < N){
				if(adj[ny][nx] == 1 && b > 0){
					visit[ny][nx][b - 1] = visit[y][x][b] + 1;
					q.push({ { ny, nx }, b - 1 });
				}
				else if(adj[ny][nx] == 0 && visit[ny][nx][b] == 0){
					visit[ny][nx][b] = visit[y][x][b] + 1;
					q.push({ { ny, nx }, b });
				}
			}
		}
	}
	
	return -1;
}

int main() {
	int N, M;
	std::cin >> N >> M;
	
	for(int i=0;i<N;++i){
		std::string room;
		std::cin >> room;
		
		for(int j=0;j<M;++j) adj[i][j] = room[j] - '0';
	}
	
	std::cout << bfs(N, M, 1);
}