Coding_Test_C++

BaekJoon 14442번: 벽 부수고 이동하기 2(C++)

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

 

14442번: 벽 부수고 이동하기 2

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

www.acmicpc.net

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) k번 벽을 허물 수 있으므로, visited배열을 3차원 배열로 선언하였다. 허물지 않고 진행한 경우 wall이라는 변수를 현재 상태 그대로, 허문 경우는 wall+1로 두어서, 최대로 허물 수 있는 한도를 넘지 않도록 코드를 작성하였다. (3차원 배열로 작성하지 않는 경우 문제가 발생한다.)

3) queue는 x값, y값, 현재 이동 횟수, 벽을 부순 횟수를 넣어서 반복을 시켰으며, BFS 기반의 알고리즘이기에 최종 목적지 값이 가장 빨리 나오는 경우가, 가장 최소 이동 횟수가 될 것이기에, 값이 나오는 순간 return 시켰다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, m,k;
int arr[1001][1001];
bool visited[1001][1001][11];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
void bfs(int a, int b)
{
	queue < pair<int, pair<int, pair<int,int>>>> q;
	visited[a][b][0] = true;
	q.push({ a,{b,{1,0}} });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second.first;
		int wall = q.front().second.second.second;
		q.pop();
		if (nowX == n && nowY == m)
		{
			cout << cnt;
			return;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX<1 || nextY<1 || nextX>n || nextY>m)
				continue;
			if (arr[nextX][nextY] == 0 && !visited[nextX][nextY][wall])
			{
				visited[nextX][nextY][wall] = true;
				q.push({ nextX,{nextY,{cnt + 1,wall}} });
			}
			if (arr[nextX][nextY] == 1 && wall + 1 <= k && !visited[nextX][nextY][wall + 1])
			{
				visited[nextX][nextY][wall + 1] = true;
				q.push({ nextX,{nextY,{cnt + 1,wall + 1}} });
			}
		}
	}
	cout << -1;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m>>k;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
			arr[i][j + 1] = s[j] - '0';
	}
	bfs(1, 1);

}