[Baekjoon] 6087번 레이저 통신.cpp

[백준] 6087번 레이저 통신 문제 링크

· 최초 아이디어 (틀린 아이디어)

특정 정점에 접근했을 때 이동할 수 있는 다음 정점의 {좌표, 필요한 최소 거울 갯수, 시작점으로부터의 거리, 직전 레이저 방향}을 저장하는 구조체를 만들었다. 각 레이저 방향을 4비트에 하상우좌 순으로 표현하였으며, 이 정보를 visit 배열에 최소 거울 갯수와 함께 저장하였다.

즉, 특정 정점의 visit 정보가 { 1, 3 }이라면 해당 정점까지 도달하는 데 3개의 거울이 사용되었으며, 아래 방향에서 진입하는 레이저 정보가 있었다는 것이다. 그 정점에서 다음으로 이동할 때 아래 방향으로는 거울 갯수를 늘리지 않고 큐에 정점 정보를 삽입하며, 그 외 방향에 대해서는 거울 갯수를 늘리며 큐에 정점 정보를 삽입한다.

이외에도 다양한 예외처리를 해주었지만 코드가 너무 복잡해져 일일이 설명하기가 힘들어졌고, 로직에 큰 문제가 없는 것 같지만 틀린 이유를 찾기 어려워졌다.

여러 테스트케이스를 만들어 입력해보았지만 디버그 과정까지 문제 없는 것 같아 보인다. 하지만 답은 틀리다고 나온다.

아래는 최초 아이디어의 소스코드이다.

#include <iostream>
#include <queue>
#define D 1
#define U 2
#define R 4
#define L 8

struct Coordinate {
   int row;
   int col;
   int mirrorCount;
   int distance;
   int prevDirection;

   bool operator < (const Coordinate& c) const {
      if (distance == c.distance) {
         return mirrorCount > c.mirrorCount;
      }
      else {
         return distance > c.distance;
      }
   }
};

std::pair<int, int> direction[16];
std::priority_queue<Coordinate> q;

int w, h;
int goalRow, goalCol;

int minMirrorNum = 100000;

int map[103][103] = { 0, };
std::pair<int, int> visit[103][103];

std::pair<int, int> startPoint;

void init() {
   direction[1] = { 1, 0 };
   direction[2] = { -1, 0 };
   direction[4] = { 0, 1 };
   direction[8] = { 0, -1 };

   for (int row = 0; row <= h + 1; row++) {
      for (int col = 0; col <= w + 1; col++) {
         map[row][col] = '*';
         visit[row][col] = { 0, 100000 };
      }
   }
}

void bfs() {
   while (!q.empty()) {
      int curRow = q.top().row;
      int curCol = q.top().col;
      int curDistance = q.top().distance;
      int curMirrorCnt = q.top().mirrorCount;
      int prevDir = q.top().prevDirection;

      if ((curRow == goalRow && curCol == goalCol) || visit[curRow][curCol].second < curMirrorCnt) {
         q.pop();
         continue;
      }
      q.pop();

      for (int count = 1; count < 16; count <<= 1) {
         int nextRow = curRow + direction[count].first;
         int nextCol = curCol + direction[count].second;

         bool isNeededMirror = !(visit[curRow][curCol].first & count);
         int nextMirrorCnt = curMirrorCnt + isNeededMirror;
         if (visit[nextRow][nextCol].second >= nextMirrorCnt && map[nextRow][nextCol] != '*') {
            q.push({ nextRow, nextCol, nextMirrorCnt, curDistance + 1, count });
            visit[nextRow][nextCol].first += count;
            visit[nextRow][nextCol].second = nextMirrorCnt;
         }
      }
      visit[curRow][curCol].first = 0;
   }
}

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

   std::cin >> w >> h;

   init();

   char ch;
   for (int row = 1; row <= h; row++) {
      for (int col = 1; col <= w; col++) {
         std::cin >> ch;
         map[row][col] = ch;
         if (map[row][col] == 'C') {
            q.push({ row, col, 0, 0, 0 });
         }
      }
   }
   goalRow = q.top().row;
   goalCol = q.top().col;
   q.pop();

   bfs();
   std::cout << visit[goalRow][goalCol].second - 1;
}

· 최종 아이디어 (정답 아이디어)

아예 로직을 바꿀 필요성을 느꼈다. 골드3 문제가 이렇게 복잡할리가 없다. 어차피 레이저는 직선으로 뻗어나가며 벽('*')을 만났을 때 꺾으면 된다. 따라서 최초 지점부터 벽을 만날 때까지 계속 진행한다. 이때 거치는 정점들을 모두 큐에 넣고 visit 배열에 몇 번의 방향 전환이 있었는지만 검사한다. 즉, visit 배열이 최소 거울 갯수를 표현하는 변수가 된다.

큐에서 요소를 꺼냈다면 방향 전환이 일어난다는 뜻이므로 일시적으로 visit 값을 1 증가시킨다. visit 값을 증가시키는 것은 '해당 정점에서부터 출발했을 때' 필요한 거울 갯수를 세기 위함이다.

그 값보다 더 큰 visit 값을 갖는 방향이 있다면 더 적은 거울 갯수로 레이저를 발사할 수 있다는 뜻이므로 visit 배열을 최신화하며 진행 가능한 정점들을 다시 큐에 삽입한다. 해당 정점에서 이동할 수 있는 모든 정점을 검사했다면 다시 visit 값을 원래대로 감소시킨다. visit 값을 원래대로 감소시키는 것으로 '해당 정점에서 출발했을 때'의 최소 거울 갯수가 아닌 '해당 정점까지 도달하는 데' 필요한 최소 거울 갯수를 표현한다.

아래는 정답 코드 전문이다.

#include <iostream>
#include <queue>

std::pair<int, int> direction[4] = { {0, 1}, {0, -1}, {1, 0}, {-1,0} };

std::queue<std::pair<int, int>> q;
int w, h;

int goalRow, goalCol;

int map[102][102] = { 0, };
int visit[102][102] = { 0, };

void init() {
	for (int row = 0; row <= h + 1; row++) {
		for (int col = 0; col <= w + 1; col++) {
			map[row][col] = '*';
			visit[row][col] = 10001;
		}
	}
}

void bfs() {
	while (!q.empty()) {
		int curRow = q.front().first;
		int curCol = q.front().second;
		visit[curRow][curCol] += 1;
		q.pop();

		for (auto dir : direction) {
			int nextRow = curRow + dir.first;
			int nextCol = curCol + dir.second;

			int tempRow = nextRow;
			int tempCol = nextCol;
			while (map[tempRow][tempCol] != '*' && visit[tempRow][tempCol] >= visit[curRow][curCol]) {
				q.push({ tempRow, tempCol });
				visit[tempRow][tempCol] = visit[curRow][curCol];
				tempRow += dir.first;
				tempCol += dir.second;
			}
		}
		visit[curRow][curCol] -= 1;
	}
}

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

	std::cin >> w >> h;

	init();

	char c;
	for (int row = 1; row <= h; row++) {
		for (int col = 1; col <= w; col++) {
			std::cin >> c;
			map[row][col] = c;
			if (c == 'C') {
				q.push({ row, col });
			}
		}
	}
	goalRow = q.front().first;
	goalCol = q.front().second;
	q.pop();

	visit[q.front().first][q.front().second] = -1;
	bfs();

	std::cout << visit[goalRow][goalCol];
}