[BOJ 26076, 조금 어려움] 곰곰이의 식단 관리 2 (C++)

제일 알고리즘 공부 열심히 하던 시기에 꼭 풀고싶었는데 못풀었던 문제다

0-1 bfs에 대해 공부중 관련 문제에 이게 뜨기도 했고

무조건 될 거 같은 아이디어가 생각나서 풀었음

 

일반적인 bfs와 다른 발상이 필요한 문제다 보니 아이디어를 떠올리기 다소 어렵다고 생각한다.

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

 

가장 기본적인 bfs문제는 1,1 점에서 N,M점까지 이동하기 위해 최소 몇칸을 이동해야 하는지 계산한다.

그렇지만 이 문제는 발상을 반대로 해서, 1,1점에서 N,M 점까지 절대 이동하지 못하게 하기 위해

최소 몇개의 벽을 놓아야 하는가에 대해 계산하는 문제이다.

 

간단한 관찰을 거치면 답은 0,1,2중에 무조건 존재함을 알 수 있다.(그래서 애드혹 태그가 붙은듯)

그리고 아이디어를 짜내면 이 문제는

이런식으로 되어있는 격자판을 가로세로로 한칸씩 확장해서,

이렇게 되어있는 그래프로 바꾸고, 오른쪽 위에 있는 벽과 좌측 아래에 있는 벽을 연결하는 문제로 바꿀 수 있으며,

이러한 문제는 (0,M+1) 점부터 (N+1,0)까지 벽을 기준으로 탐색하며 연결하는 bfs문제로 해결이 가능하다. 이때 bfs는 상하좌우+대각선 방향의 8개 방향으로 진행해야 한다.

바깥쪽 벽을 완전히 다 두르지 않고 좌측 위와 우측 아래를 끊은 이유는,

일단 벽을 완전히 다 두를 경우 답이 0으로만 나오게 되기 때문이다. 벽을 저렇게 설정해 놓고 시작/끝점을 방문할 수 없도록 예외처리해 놓으면 0,1,2로 답이 나오는 모든 경우를 탐색할 수 있다.

 

그리고 여기서 0-1 bfs에 대해 알고 있다면 메모리와 시간 비용을 크게 줄일 수 있다.

0-1 bfs에 대해 간단히 설명하자면 0과 1로만 배열이 주어지는 최단 거리 탐색 문제에서(보통은 이때 다익스트라를 사용한다) deque의 장점을 활용해, 비용이 증가하는 탐색은 후순위로(queue처럼) 밀어넣고, 비용이 증가하지 않는 탐색은 우선순위로(stack)처럼 밀어넣으며 빠르게 최단거리를 찾아내는 방법이다.

다른 블로그에 좋은 글들이 많으니 구글링 ㄱㄱ

 

그래서 내 코드는 아래와 같다

 

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int N,M;
int arr[2003][2003];
int vis[2003][2003];
const int dx[8]={1,1,0,-1,-1,-1,0,1};
const int dy[8]={0,1,1,1,0,-1,-1,-1};
int main(){
	fastio;
	//답은 무조건 0 또는 1 또는 2
	//오른쪽 위부터 좌측 아래까지
	//단절시키기 위한 0-1 bfs를 진행한다.
	//bfs는 8방향으로 진행 가능하다
	cin>>N>>M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin>>arr[i][j];
		}
	}
	for (int i = 2; i <= M+1; i++)arr[0][i]=1;
	for (int i = 0; i <= M-1; i++)arr[N+1][i]=1;
	for (int i = 2; i <= N; i++)arr[i][0]=1;
	for (int i = 1; i <= N-1; i++)arr[i][M+1]=1;
	
	deque<tuple<int,int,int>> dq; //y,x,지나온빈공간개수
	dq.push_back({0,M+1,1});
	vis[0][M+1]=1;
	while (!dq.empty())
	{
		auto [cy,cx,cc] = dq.front();
		dq.pop_front();
		if(cy==N+1&&cx==0)break;//단절조건달성
		for (int i = 0; i < 8; i++)
		{
			int ny = cy+dy[i];
			int nx = cx+dx[i];
			if(ny<0||nx<0||ny>N+1||nx>M+1)continue;
			if(ny==1&&nx==1)continue;
			if(ny==N&&nx==M)continue;
			int nc = cc+!(arr[ny][nx]);
			if(vis[ny][nx]>0&&vis[ny][nx]<=nc)continue;
			//0-1 bfs에 따라, 벽이면 front로 넣고 빈공간이면 back으로 넣기
			if(arr[ny][nx]){//벽
				vis[ny][nx]=nc;
				dq.push_front({ny,nx,nc});
			}
			else{
				vis[ny][nx]=nc;
				dq.push_back({ny,nx,nc});
			}
		}
	}

	cout<<vis[N+1][0]-1;
	return 0;
}