[BFS] 벽 부수고 이동하기

예제 입력 1

6 4

0100

1110

1000

0000

0111

0000

예제 출력 1

15

예제 입력 2

4 4

0111

1111

1111

1110

예제 출력 2

-1

 

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

2206번: 벽 부수고 이동하기

- 어떤 칸에 방문했음을 체크+거리 계산시 벽을 부순적이 있는 경우/부순적이 없는 경우로도 추가로 나눠준다. (dist[next.r][next.c][now.z], R = row, C = column, Z = 벽을 부쉈는지)

- 아직 부수지 않은 상태에서 부수고 지나갈 경우, 방문하려는 칸을 부수고 지나갔을 경우를 체크했는지를 체크해야 한다. (뚫고갔던 적이 있는지(dist[next.r][next.c][1]를 검사해야한다.)

#include <stdio.h>

const int MAX_QUEUE_SIZE = 2000;
const int MAX_SIZE = 1000;
const int DIRECTION_COUNT = 4;

int map[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE][2];

int R, C;

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

class Tuple
{
public:
	int r;
	int c;
	int z;

	Tuple() { r = c = z = 0; }

	Tuple(int r, int c, int z) : r(r), c(c), z(z)
	{
	}

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

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

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T item[MAX_QUEUE_SIZE];
	
public:
	Queue() { front = rear = 0; }

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

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

		return result;
	}

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

void BFS(Tuple start, Tuple target)
{
	dist[start.r][start.c][start.z] = 1;
	q.push(start);

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

		if (now == target)
		{
			printf("%d\n", dist[now.r][now.c][now.z]);
			return;
		}

		for (int i = 0; i < DIRECTION_COUNT; i++)
		{
			Tuple next(now.r + dR[i], now.c + dC[i], now.z);

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

			if (map[next.r][next.c] == 0 && dist[next.r][next.c][next.z] == -1)
			{
				dist[next.r][next.c][next.z] = dist[now.r][now.c][now.z] + 1;
				q.push(next);
			}

			// 아직 벽을 통과한적 없고 다음에 가려는 곳이 벽 : 뚫고갔던 적이 있는지(dist[next.r][next.c][1]를 검사해야한다.
			if (next.z == 0 && map[next.r][next.c] == 1 && dist[next.r][next.c][1] == -1)
			{
				Tuple anotherNext(next.r, next.c, 1);
				dist[next.r][next.c][1] = dist[now.r][now.c][now.z] + 1;

				q.push(anotherNext);
			}
		}
	}

	printf("-1\n");
}

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

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

			for (int z = 0; z < 2; z++)
				dist[i][j][z] = -1;
		}
	}

	Tuple now(0, 0, 0);
	Tuple target(R - 1, C - 1, 0);

	BFS(now, target);

	return 0;
}