[BFS] 레이저 통신

예제 입력 1

7 8

.......

......C

......*

*****.

....*..

....*..

.C..*..

.......

예제 출력 1

3

 

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

6087번: 레이저 통신

- 거리가 중요한 것이 아니고 방향을 바꾸는 횟수를 최소화 하는 것이 목적이므로, 상하좌우로 더이상 이동할 수 없을 때까지 모두 동일한 거리로 대입하고 큐에 넣는다. 큐에서 꺼내고 다시 상하좌우로 이동할 때 방향이 바뀌는 것이므로 거리를 + 1하여 저장하는 식으로 처리한다.

 

- 답은 -1을 해줘야한다. 선분의 개수가 아닌 꺾이는 횟수이기 때문.

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

constexpr int MAX_SIZE = 101;
constexpr int MAX_QUEUE_SIZE = 20000;

int R, C;
char map[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE];

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

int result = 10000000;

class Point
{
public:
	int r;
	int c;

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

	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);
	}
};
Point equipment[2];

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

public:
	Queue() { rear = front; }

	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;

int BFS()
{
	dist[equipment[0].r][equipment[0].c] = 0;
	q.push(equipment[0]);

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

		if (now == equipment[1])
		{
			result = MIN(result, dist[now.r][now.c]);
		}

		for (int i = 0; i < 4; i++)
		{
			int moveCnt = 1;

			while (true)
			{
				Point next(now.r + (dR[i] * moveCnt),
					now.c + (dC[i] * moveCnt));

				if (!next.IsInBoundary(R, C)) break;
				if (map[next.r][next.c] == '*') break;
				if (dist[next.r][next.c] == -1)
				{
					dist[next.r][next.c] = dist[now.r][now.c] + 1;
					q.push(next);
				}

				moveCnt++;
			}
		}
	}

	return result-1;
}

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

	int equipmentIdx = 0;

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

				if (map[i][j] != '\n') break;
			}

			dist[i][j] = -1;

			if (map[i][j] == 'C')
			{
				equipment[equipmentIdx].r = i;
				equipment[equipmentIdx].c = j;
				equipmentIdx++;
			}
		}
	}

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

	return 0;
}