[BOJ/백준 6087/C++] 레이저 통신

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

6087번: 레이저 통신

 

[문제 요약]

- 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

- 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

 

- 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

 

[문제 조건]

- 첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

- 둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

- 'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

- 시간 제한 : 1초

- 메모리 제한 : 128MB

 

[문제 풀이]

필자는 이 문제를 풀다가 메모리제한에 걸렸었다.

 

먼저 문제의 큰 아이디어는 하나의 C지점에서 시작하여 두번째 C지점 까지 최소한의 방향 전환으로 갈 수 있는 방법을 구하는 것이다. 다시 말하면 최대한 적게 꺾어서 두번째 C지점 까지 도달해야 하는 것이다.

 

메모리 제한에 걸렸던 방법은 다음과 같다.

• 하나의 C지점에서 시작하여 BFS + 다익스트라 방식을 이용하여 탐색해 나간다.
• 갱신 조건은 다음과 같다.
  • 이동 방향이 같은 경우 다음지점까지의 횟수가 현재지점까지의 횟수보다 크거나 같을 경우 현재지점의 횟수로 갱신
  • 이동 방향이 바뀔 경우 다음지점까지의 횟수가 (현재지점까지의 횟수 + 1)보다 크거나 같을 경우 현재지점의 횟수로 갱신

위와 같은 방법으로 작성하였는데 76퍼쯤에서 최대한 최적화를 시켜도 메모리초과가 나게 된다. 물론 또 다른 방법으로 최적화를 했으면 됐을수도 있지만 필자는 실패했다.

 

[실패 코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int W, H;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<char>> origin_mp;
vector<vector<int>> dt;
vector<pii> lazor;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> W >> H;
	origin_mp.resize(H); dt.resize(H);
	for (int i = 0; i < H; i++)
	{
		origin_mp[i].resize(W);
		dt[i].resize(W);
	}

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> origin_mp[i][j];
			if (origin_mp[i][j] == 'C') lazor.push_back({ i,j });
			dt[i][j] = INF;
		}
	}

	queue<pair<pii, pii>> pq;
	dt[lazor[0].first][lazor[0].second] = -1;
	for (int i = 0; i < 4; i++)
	{
		int nx = lazor[0].second + dx[i];
		int ny = lazor[0].first + dy[i];
		if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
		if (origin_mp[ny][nx] == '*')continue;
		dt[ny][nx] = 0;
		pq.push({ {0,i},{ny, nx} });
	}
	while (!pq.empty())
	{
		pii coordinate = pq.front().second;
		pii info = pq.front().first;
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = coordinate.second + dx[i];
			int ny = coordinate.first + dy[i];
			int cnt = info.first;

			if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
			if (origin_mp[ny][nx] == '*') continue;
			if (i != info.second) cnt = cnt + 1;

			if (dt[ny][nx] >= cnt)
			{
				dt[ny][nx] = cnt;
				pq.push({ {cnt,i},{ny,nx} });
			}
		}
	}

	cout << dt[lazor[1].first][lazor[1].second];
}

 

따라서 살짝 다른 방법으로 접근하였다.

 

다른 방법은 다음과 같다.

• 하나의 C지점에서 시작하여 4개의 방향 각각 벽을 만나거나 맵을 넘어가는 경우때까지 일직선으로 같은 값으로 갱신한다. 갱신한 지점들은 방문체크 + 큐에 넣어준다.

위 방법의 경우 어차피 한 지점에서 레이저를 발사하면 그 방향과 같은 수직, 수평선상에 놓인 지점들은 모두 같은 값을 가질 수 밖에 없다. 따라서 처음의 경우와 비교했을 때 확인하는 지점의 수를 줄일 수 있었다.

 

[성공 소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int W, H;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
char origin_mp[101][101];
int dt[101][101];
bool ck[101][101];
vector<pii> lazor;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> W >> H;
	
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> origin_mp[i][j];
			if (origin_mp[i][j] == 'C') lazor.push_back({ i,j });
			dt[i][j] = INF;
		}
	}

	queue<pii> pq;
	pq.push({ lazor[0].first,lazor[0].second });
	ck[lazor[0].first][lazor[0].second] = true;
	dt[lazor[0].first][lazor[0].second] = 0;

	while (!pq.empty())
	{
		pii coordinate = pq.front();
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = coordinate.second + dx[i];
			int ny = coordinate.first + dy[i];
			while (nx >= 0 && ny >= 0 && nx < W && ny < H)
			{
				if (origin_mp[ny][nx] == '*') break;

				if (!ck[ny][nx])
				{
					ck[ny][nx] = true;
					dt[ny][nx] = dt[coordinate.first][coordinate.second] + 1;
					pq.push({ny,nx});
				}
				nx += dx[i];
				ny += dy[i];
			}
		}
	}

	cout << dt[lazor[1].first][lazor[1].second] - 1;
}

메모리 초과 해결할려고 구글링해서 찾은 코드도 메모리 초과가 걸리는 코드여서 삽질 엄청했다.......

굳