💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 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);
}

이번문제는 알고리즘초보인 저에게는 매우 도움이 된 문제였다고 생각합니다.
사실 저가 bfs, 최대유량, 그래프문제만 풀어서 꽤 많이 풀고있다고 생각했는데, 아직 멀었나보군요...
이런 유형의 문제는 처음풀어보았기에 재미있었고 유익했습니다.

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~