Algorithm/문제풀이

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

lee308812 2019. 10. 19. 17:31

 

예제 입력 1

1 4 1

0010

예제 출력 1

5

예제 입력 2

1 4 1

0100

예제 출력 2

4

예제 입력 3

6 4 1

0100

1110

1000

0000

0111

0000

예제 출력 3

15

예제 입력 4

6 4 2

0100

1110

1000

0000

0111

0000

예제 출력 4

9

 

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

 

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

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

www.acmicpc.net

 

- 추가된 조건은, 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다를 처리해 주어야 한다. 처음에는 해당 조건을 처리하기 위해 현재 밤일 경우 다음 칸의 밤 이동 거리를 + 2 해주었는데 정답이 아닌듯. 그냥 가만히 있는 경우로 처리 하여야 한다.

// 가만히 있는게 가능할 경우
if (dist[now.r][now.c][now.k][!now.night] == 0)
{
	dist[now.r][now.c][now.k][!now.night] = dist[now.r][now.c][now.k][now.night] + 1;
	now.night = !now.night;
	q.push(now);
}

 

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

constexpr int MAX_SIZE = 1000;
constexpr int MAX_QUEUE_SIZE = MAX_SIZE * 100;
constexpr int MAX_BRAKE_SIZE = 11;

int R, C, K;
int map[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE][MAX_BRAKE_SIZE][2];

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

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

	Point() {}
	Point(int r, int c, int k, bool night) : r(r), c(c), k(k), night(night) {}

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

	bool operator==(Point other)
	{
		return (r == other.r) && (c == other.c);
	}
};

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

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

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

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

		return result;
	}

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

void BFS()
{
	int ans = -1;

	Point target(R-1, C-1, 0, 0);

	Point start(0, 0, 0, false);
	dist[0][0][0][false] = 1;
	q.push(start);

	while (!q.isEmpty())
	{
		Point now = q.pop();

		if (now == target)
		{
			if (ans == -1) ans = dist[now.r][now.c][now.k][now.night];
			else ans = MIN(ans, dist[now.r][now.c][now.k][now.night]);
		}

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

			if (!next.IsInBoundary(R, C)) continue;

			if (dist[next.r][next.c][next.k][next.night] == 0 && map[next.r][next.c] == 0)
			{
				dist[next.r][next.c][next.k][next.night] = dist[now.r][now.c][now.k][now.night] + 1;
				q.push(next);
			}
			// 부순 뒤에는 낮이 되어야 한다.
			else if (next.k + 1 <= K && next.night == true && dist[next.r][next.c][next.k + 1][next.night] == 0 && map[next.r][next.c] == 1)
			{
				next.k++;
				dist[next.r][next.c][next.k][next.night] = dist[now.r][now.c][now.k][now.night] + 1;
				q.push(next);
			}
		}

		// 가만히 있는게 가능할 경우
		if (dist[now.r][now.c][now.k][!now.night] == 0)
		{
			dist[now.r][now.c][now.k][!now.night] = dist[now.r][now.c][now.k][now.night] + 1;
			now.night = !now.night;
			q.push(now);
		}
	}

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

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;
}

 

'Algorithm > 문제풀이' 카테고리의 다른 글

[BFS] 탈출  (0) 2019.10.24
[BFS] 움직이는 미로 탈출  (0) 2019.10.23
[BFS] 벽 부수고 이동하기 2  (0) 2019.10.16
[BFS ] 벽 부수고 이동하기 4  (0) 2019.10.16
[BFS] 벽 부수고 이동하기  (0) 2019.10.15