백준 6087번 레이저 통신 (C++)

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

6087번: 레이저 통신

 
BFS , 다익스트라 문제이다. 사실 다익스트라의 정확한 정의를 모르겠다. 이 문제는 최단거리이긴 하지만 무조건 최단으로 가면 안되고 조건이 추가되었고 그 조건이 분기점이 된다. 그냥 조건이 있어도 최단거리라는 조건과 배열을 통한 조건이 있다면 다익스트라 라고 하는 것일까 ? 이건 잘 모르겠다.
아무튼, 많은 틀렸습니다와 시간초과 메모리초과 날 수 있는 건 다 났던 문제였다. 왜 정답률이 낮았는지 알 것 같고 내가 거들었다.
 
1. 문제 조건
- 최단거리로 C에서 C까지 이동한다.
- 방향이 바뀔 경우 거울을 새운다.
- 거울의 갯수가 최소갯수를 출력한다. 
 
2. 내 접근법
- 문제를 보고 먼저 bfs생각이 났다. 그리고 방향을 기억해야하고 지금까지 거울을 몇 개 설치했는지 알고 있어야한다. 그리고 각 좌표마다 의자의 갯수를 저장해놓고 큐의 push조건으로 거울의 갯수가 지금 좌표와 같거나 크면 더 개선할 여지가 있으므로 푸쉬하도록 했다. 그리고 마지막 정답을 mirror[lastx][lasty] 하면 정답일 것이라 생각했다. 그러나 이 방법은 어떤 사람의 저격 데이터 추가로 80퍼센트에서 시간 및 메모리 초과가 난다. 그러나 이 방식이 틀린 것은 아니다. 올바른 접근법이긴 하나 한가지를 더 생각해야했다.
 
3. 올바른 접근법
- 방향이 존재한다는 것을 잘 생각해야한다. 만약 mirror[][] 2차원 배열로 거울의 갯수를 저장했다고 하자. 그리고 동쪽에서 2번의 거울을 갖고오고 서쪽에서 3번의 거울을 가지고 온다고 하자. 그렇다면 동쪽에서 거울 두번을 갖고 왔으므로 서쪽에서 온 것은 컷된다. 매우 효율적으로 보이지만 이 방법은 만약 동쪽과 서쪽 모두 2개씩 갖고 온다면 이후 개선될 여지가 있기 때문에 각 방향에서 같은 개수의 거울을 들고오면 모두 큐에 넣어줘야한다. 즉,
 
if : mirror[x][y] >= cnt 
    push
 
가 되기 때문에 같은 연산을 여러번 하게 될 수 있다. 그리고 개선될지 안될지도 모르는데 불필요한 연산이 많이 추가된다.
때문에 mirror[x][y][point] 이렇게 방향까지 담겨있는 3차원 배열을 선언해야한다.  그렇다면 각 방향마다 갱신을 하고 있기 때문에 동쪽과 서쪽에서 모두 2를 가져와도 만약 동쪽으로 왔을 때의 거울이 이미 1개로 되어 있다면 푸쉬하지 않고 서쪽에서 온 2만 큐에 담기게 되어 훨씬 연산을 줄일 수 있다.
 
if : mirror[x][y][point] > cnt
   push
 
 
sk를 만약 이 문제를 풀고서 만났다면 코테 문제를 풀었을 것 같다.. 진짜 백준 열심히 해야한다.
 

#include <iostream>
#include <queue>

using namespace std;
int N, M, start_x, start_y, end_x, end_y;
int mirror[101][101][4];
char board[101][101];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin >> N >> M;
	int ch = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'C') {
				if (ch == 0) {
					start_x = i;
					start_y = j;
					ch++;
				}
				else {
					end_x = i;
					end_y = j;
				}
			}
			for(int k = 0; k < 4; k++)
			    mirror[i][j][k] = 1231321;
		}
	}

	queue<pair<pair<int, int>, pair<int, int>>> q;
    for(int i = 0; i < 4; i++){
	    q.push({ {start_x, start_y},{0,i} });
	    mirror[start_x][start_y][i] = 0;
    }
    
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second.first;
		int point = q.front().second.second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int ncnt = cnt;
			if (nx < M && nx > -1 && ny < N && ny > -1 && board[nx][ny] != '*') {
				if (point != i) ncnt++;
				if (mirror[nx][ny][i] > ncnt) {
					mirror[nx][ny][i] = ncnt;
					q.push({ {nx,ny}, {ncnt, i} });
				}
			}
		}
	}
	int answer = 123124314;
	for(int i = 0; i < 4; i++){
        answer = min(answer, mirror[end_x][end_y][i]);
    }
    
    cout << answer;

}

진짜 정신이 나가버릴 뻔 했다..