[C++] 백준 13460번: 구슬 탈출 2

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

13460번: 구슬 탈출 2

시뮬레이션과 너비 우선 탐색을 통해 문제를 풀어볼 것이다.

보드의 정보가 입력된다. R은 빨간공, B는 파란공, O는 목적지를 나타내며 #은 벽을 나타낸다.

먼저, 이러한 정보를 어떻게 효율적이고 깔끔하게 다룰 수 있을지 고민해보자.

클래스를 하나 정의하여 사용해보면 가독성이 좋아지지 않을까.

성능은 일단 제쳐두고 가독성만을 생각하며 코드를 작성해보자.

새로 정의할 클래스의 이름은 Snapshot이다.

수많은 분기 중 한 순간의 상태를 나타낸다는 의미다.

멤버 변수는 다음과 같은 것들을 갖는다.

• 현재 상태에 도달하기까지 동작한 횟수
• 벽의 위치와 목적지를 저장한 N*M 크기의 2차원 배열
• 빨간공의 현재 위치
• 파란공의 현재 위치

벽의 위치와 목적지를 저장하는 배열은 그 내용이 바뀌지 않으므로 static으로 선언한다.

그 배열은 클래스 외부에서 초기화하고, 해제도 클래스 외부에서 하도록 한다.

멤버 함수로는 다음과 같은 것들을 갖는다.

• 위로 기울이기
• 아래로 기울이기
• 왼쪽으로 기울이기
• 오른쪽으로 기울이기

세부적으로 필요한 helper function들은 작성하면서 생각하기로 하자.

기울이기 함수를 private로 선언하고 인수로, 세로와 가로 방향을 받도록 했다.

기울일 때, 두 공 중 하나가 경로를 가로막고 있으면 그 공 부터 움직여 줘야한다.

아니면 동시에 움직이도록 해볼까? 생각해보니 그것도 괜찮은 생각인 것 같다.

하지만 둘 중 하나가 먼저 벽에 닿고, 나머지는 계속 움직일 수 있는 상황에는 어떻게 해야할까.

각 공에 대해 벽에 닿았는지 여부를 나타내는 bool 변수를 선언하여 활용해야겠다.

클래스는 대충 아래와 같은 모습이다.

class Snapshot {
private:
	bool Tilt(int vertical, int horizontal){ ... }

public:
	static int N, M;
	static char** board;
	int level;
	int* red, * blue;

	Snapshot() { ... }

	Snapshot(Snapshot& other) { ... }

	~Snapshot() { ... }

	bool TiltUpward() {
		return Tilt(-1, 0);
	}

	bool TiltDownward() {
		return Tilt(1, 0);
	}

	bool TiltLeftward() {
		return Tilt(0, -1);
	}

	bool TiltRightward() {
		return Tilt(0, 1);
	}
};

나름 깔끔하게 작성된 것 같다.

이제 이를 활용하여 문제를 풀어볼 차례다.

입력은 다음과 같이 받는다.

Snapshot initBoard;
cin >> Snapshot::N >> Snapshot::M;
Snapshot::board = new char* [Snapshot::N];
FOR(r, Snapshot::N) {
    Snapshot::board[r] = new char[Snapshot::M];
    FOR(c, Snapshot::M) {
        cin >> Snapshot::board[r][c];
        if (Snapshot::board[r][c] == 'R') {
            initBoard.red[0] = r;
            initBoard.red[1] = c;
        }
        if (Snapshot::board[r][c] == 'B') {
            initBoard.blue[0] = r;
            initBoard.blue[1] = c;
        }
    }
}

다음으로 너비 우선 탐색을 해야하는데, 큐에는 Snapshot 인스턴스를 담으면 된다.

그런데 방문 확인은 어떻게 해야 좋을까?

빨간공과 파란공이 동일한 상태에 있으면 중복인 상태다.

그 두 공의 위치를 저장하여 방문 확인을 해야 하는데,

4차원 배열을 사용하기 보다 map<int, bool>을 사용하여 메모리를 절약해보자.

두 공의 좌표에 4차원 배열 인덱스를 계산하듯 적절한 값을 곱하여 키값을 계산했다.

int getKey(int*& red, int*& blue) {
	int& N = Snapshot::N;
	int& M = Snapshot::M;
	int key = blue[1];
	key += blue[0] * M;
	key += red[1] * N * M;
	key += red[0] * M * N * M;
	return key;
}

보드를 기울였을 때의 처리를 구현해야 한다. 주의할 점으로는...

• 빨간공이 들어간 이후 파란공이 들어가면 안 된다.
• 유효한 범위 이내에서 공이 움직여야 한다.
• 벽을 뚫으면 안 된다.
• 둘 중 하나의 공이 벽에 닿아 멈추더라도 남은 공의 움직임을 지속한다.

이에 유의하며 작성한 Tilt 함수는 아래와 같다.

bool Tilt(int vertical, int horizontal) {
    bool isRedTouched = false;
    bool isBlueTouched = false;

    bool isRedReached = false;
    bool isBlueReached = false;

    int currentRedPos[] = { red[0], red[1] };
    int currentBluePos[] = { blue[0], blue[1] };

    while (!isRedTouched || !isBlueTouched) {
        if (!isRedReached) {
            red[0] += vertical;
            red[1] += horizontal;

            if (red[0] < 0 || red[0] == N || red[1] < 0 || red[1] == M ||
                (red[0] == blue[0] && red[1] == blue[1]) ||
                board[red[0]][red[1]] == '#') {
                isRedTouched = true;
                red[0] -= vertical;
                red[1] -= horizontal;
            }

            if (board[red[0]][red[1]] == 'O') {
                isRedReached = true;
                isRedTouched = true;
            }
        }

        if (!isBlueTouched) {
            blue[0] += vertical;
            blue[1] += horizontal;

            if (blue[0] < 0 || blue[0] == N || blue[1] < 0 || blue[1] == M ||
                (!isRedReached && red[0] == blue[0] && red[1] == blue[1]) ||
                board[blue[0]][blue[1]] == '#') {
                isBlueTouched = true;
                blue[0] -= vertical;
                blue[1] -= horizontal;
            }

            if (board[blue[0]][blue[1]] == 'O') {
                isBlueReached = true;
                break;
            }
        }
    }

    level++;

    if (isBlueReached) {
        red[0] = currentRedPos[0];
        red[1] = currentRedPos[1];
        blue[0] = currentBluePos[0];
        blue[1] = currentBluePos[1];
        return false;
    }
    return isRedReached;
}

이제 너비우선탐색 본문을 작성해야 한다.

멤버함수를 각각 호출하기 위해 발생한 반복을 지우기 위해 멤버함수 포인터 배열을 사용했다.

int answer = -1;
map<int, bool> mark;
mark[getKey(initBoard.red, initBoard.blue)] = true;
queue<Snapshot> bfs;
bfs.push(initBoard);
bool (Snapshot:: * tilts[4])() = { &Snapshot::TiltUpward, &Snapshot::TiltDownward, &Snapshot::TiltLeftward, &Snapshot::TiltRightward };
while (!bfs.empty()) {
    Snapshot nowBoard = bfs.front();
    bfs.pop();

    for (auto& tilt : tilts) {
        Snapshot nextBoard = nowBoard;
        bool isRedReached = (nextBoard.*tilt)();

        if (isRedReached) {
            answer = nextBoard.level;
            goto OUT;
        }
        if (!mark[getKey(nextBoard.red, nextBoard.blue)]) {
            mark[getKey(nextBoard.red, nextBoard.blue)] = true;
            bfs.push(nextBoard);
        }
    }
}
OUT:
cout << (answer <= 10 ? answer : -1) << EL;

위에서 마지막 줄 답안을 출력할 때 10을 초과하는지 체크하지 않아 두 번의 오답을 받았다.