[BFS] 벽 부수고 이동하기 2

 

 

예제 입력 1

6 4 1

0100

1110

1000

0000

0111

0000

예제 출력 1

15

예제 입력 2

6 4 2

0100

1110

1000

0000

0111

0000

예제 출력 2

9

예제 입력 3

4 4 3

0111

1111

1111

1110

예제 출력 3

-1

 

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

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

 

- 거리를 잴 때, dist[r][c]로 재던것을 dist[r][c][k]로 나누어서 풀면 된다.

* r = Row, c = Column, k = 벽 부순 횟수

 

- 일반 BFS와의 또 다른 차이점은 그냥 그 지점에 도달했다고 해서 끝내면 안되고 벽을 몇번 통과했을 때가 최소가 되는지 체크해야만한다.

 

- Queue size를 충분히 잡지 않아서 계속 틀렸었음....

 

#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))

constexpr int MAX_MAP_SIZE = 1001;
constexpr int MAX_QUEUE_SIZE = MAX_MAP_SIZE * MAX_MAP_SIZE;
constexpr int MAX_BRAKE_COUNT = 11;

int map[MAX_MAP_SIZE][MAX_MAP_SIZE];
int dist[MAX_MAP_SIZE][MAX_MAP_SIZE][MAX_BRAKE_COUNT];

int R, C, K;

int dR[] = { -1, 1, 0, 0 };
int dC[] = { 0, 0, -1, 1 };

class Point
{
public:
	int r;
	int c;
	int k;

	Point() { r = c = k = 0; }
	Point(int r, int c, int k) : r(r), c(c), k(k) {}

	bool isInBoundary(int R, int C)
	{
		return (r >= 0) && (r < R) && (c >= 0) && (c < C);
	}
};

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T data[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }

	void push(T item)
	{
		data[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = data[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};
Queue<Point> q;

void BFS()
{
	Point start(0, 0, 0);
	dist[0][0][0] = 1;
	q.push(start);
	
	while (!q.isEmpty())
	{
		Point now = q.pop();

		for (int i = 0; i < 4; i++)
		{
			Point next(now.r + dR[i], now.c + dC[i], now.k);
			if (!next.isInBoundary(R, C)) continue;

			if (dist[next.r][next.c][next.k] == 0 && map[next.r][next.c] == 0)
			{
				dist[next.r][next.c][next.k] = dist[now.r][now.c][now.k] + 1;
				q.push(next);
			}
			else if (next.k + 1 <= K && dist[next.r][next.c][next.k + 1] == 0 && map[next.r][next.c] == 1)
			{
				Point anotherPoint(next.r, next.c, next.k+1);
				dist[anotherPoint.r][anotherPoint.c][anotherPoint.k] = dist[now.r][now.c][now.k] + 1;
				q.push(anotherPoint);
			}
		}
	}

	int ans = -1;

	for (int i = 0; i <= K; i++)
	{
		if (dist[R - 1][C - 1][i] != 0)
		{
			if (ans == -1)
				ans = dist[R - 1][C - 1][i];
			else if (ans > dist[R - 1][C - 1][i])
				ans = dist[R - 1][C - 1][i];
		}
	}

	printf("%d\n", ans);

	return;
}

int main(void)
{
	scanf("%d %d %d", &R, &C, &K);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}

	BFS();

	return 0;
}