[백준/BOJ] 백준 16933번 : 벽 부수고 이동하기 3

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

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

[x위치][y위치][부순 벽의 개수][낮인지 밤인지]를 고려한 bfs를 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
using namespace std;

int n, m, k;
vector<string> board;
int dxdy[5][2] = { {0,0},{0,-1},{-1,0},{0,1},{1,0} };

int discovered[1000][1000][11][2]; //[x위치][y위치][부순 벽의 개수][낮인지 밤인지]
int depth[1000][1000][11][2];

struct point {
	int x;
	int y;
	int broken; //부순 벽의 개수
	int odd_even; //1은 낮, 0은 밤
};

int Solve(pair<int, int> start, pair<int, int> dest)
{
	queue<point> q;

	for(int i=0; i<1000; i++)
		for (int j = 0; j < 1000; j++)
			for (int k = 0; k < 11; k++)
				for (int l = 0; l < 2; l++)
				{
					discovered[i][j][k][l] = 0;
					depth[i][j][k][l] = 0;
				}

	q.push({ start.first,start.second,0,1 });
	discovered[start.first][start.second][0][1] = 1;
	depth[start.first][start.second][0][1] = 1;

	while (!q.empty())
	{
		pair<int, int> here = make_pair(q.front().x, q.front().y);
		int here_broken = q.front().broken;
		int here_odd_even = q.front().odd_even;
		q.pop();

		if (here.first == dest.first && here.second == dest.second)
			return depth[here.first][here.second][here_broken][here_odd_even];

		for (int i = 0; i < 5; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			int there_broken;
			int there_odd_even = (depth[here.first][here.second][here_broken][here_odd_even] + 1) % 2;

			//머물러 있을때
			if (i == 0)
			{
				there_broken = here_broken;

				if (discovered[there.first][there.second][there_broken][there_odd_even] == 0)
				{
					discovered[there.first][there.second][there_broken][there_odd_even] = 1;
					depth[there.first][there.second][there_broken][there_odd_even] = depth[here.first][here.second][here_broken][here_odd_even] + 1;
					q.push({ there.first,there.second,there_broken,there_odd_even });
				}
				
			}

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m)
			{
				//이동 하려는 위치가 벽일때
				if (board[there.first][there.second] == '1')
				{
					//벽을 부술 수 있을때
					if (here_broken < k && here_odd_even == 1)
					{
						there_broken = here_broken + 1;

						if (discovered[there.first][there.second][there_broken][there_odd_even] == 0)
						{
							discovered[there.first][there.second][there_broken][there_odd_even] = 1;
							depth[there.first][there.second][there_broken][there_odd_even] = depth[here.first][here.second][here_broken][here_odd_even] + 1;
							q.push({ there.first,there.second,there_broken,there_odd_even });
						}
					}
				}

				else
				{
					there_broken = here_broken;

					if (discovered[there.first][there.second][there_broken][there_odd_even] == 0)
					{
						discovered[there.first][there.second][there_broken][there_odd_even] = 1;
						depth[there.first][there.second][there_broken][there_odd_even] = depth[here.first][here.second][here_broken][here_odd_even] + 1;
						q.push({ there.first,there.second,there_broken,there_odd_even });
					}
				}
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	cout << Solve(make_pair(0, 0), make_pair(n - 1, m - 1));

	return 0;
}