백준 3197 c++ "백조의 호수" -PlusUltraCode-

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

[필자 사고]

BFS 탐색문제이다. 필자는 이 문제 전에는 queue를 하나만 써오던 습관이 있었는데

ㅇㅣ 문제에서는 임시큐까지 총 4개의 큐를 사용해야 풀 수 있는 문제이다.

고정관념을 깨게 해준 문재이다.

주의할점은 먼저 오리가 탐색해야된다. 오리가 탐색한 지역은 방문처리를 하고

오리를 만날경우 끝내면 된다.

다음으로 물이 X자를 만나면 X자를 '.'으로 교체후 임시큐에 저장한다.

여기서 중요한건 물은 방문처리를 건들지 않는다는 것이다.

 

[코드 해설]

코드 설명

1. 입력 처리 및 초기화
   • Input 함수는 격자 배열(arr)의 크기 N×MN \times MN×M과 내용을 입력받습니다.
   • 배열 내의 각 좌표를 확인하며, 시작점(L)과 물이 있는 좌표(.)를 찾아 큐 wQ에 추가합니다.
   • 또한, 백조의 초기 위치(originSero, originGaro)를 저장합니다.
2. 방문 여부 초기화
   • initVisited 함수는 visited 배열을 N×MN \times MN×M 크기로 초기화하며, 모든 위치를 false로 설정합니다.
3. 범위 검사
   • isInside 함수는 좌표가 배열 범위 내에 있는지를 확인하여, 유효한 이동인지 판별합니다.
4. 물 확산 처리 (BFS)
   • waterBFS 함수는 물이 확산되는 로직을 처리합니다.
   • 큐 wQ에서 현재 물의 위치를 하나씩 꺼내, 인접한 위치를 확인합니다.
   • 인접 위치가 얼음(X)인 경우 물로 녹이며(.로 변환), 다음 확산 대상 큐(twQ)에 추가합니다.
5. 백조의 이동 처리 (BFS)
   • duckBFS 함수는 백조가 이동 가능한 영역을 탐색합니다.
   • 큐 dQ에서 현재 백조의 위치를 하나씩 꺼내, 인접한 위치를 확인합니다.
   • 방문하지 않은 위치에 대해, 만약 상대 백조(L)에 도달했다면 플래그(resultFlag)를 true로 설정하고 탐색을 종료합니다.
   • 이동 가능 영역(.)은 dQ에 추가하고, 얼음(X)은 다음 탐색 대상 큐(tdQ)에 추가합니다.
6. 게임 진행 로직
   • Game_Start 함수는 게임의 메인 루프를 담당합니다.
   • 초기화된 dQ와 visited를 이용해 백조의 BFS를 실행하고, 상대 백조를 만났다면 이동 횟수를 출력하고 종료합니다.
   • 상대를 만나지 못한 경우, waterBFS를 호출하여 얼음을 녹이고, 다음 단계의 큐(wQ, dQ)를 갱신합니다.
   • 새로운 큐(twQ, tdQ)를 초기화하며, 시간을 증가시킵니다.
7. 메인 함수
   • main 함수는 입력을 받아 게임을 시작하며, 종료 조건이 충족될 때까지 반복합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int N, M;
vector<vector<char>> arr;
vector<vector<bool>> visited;

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

int originSero, originGaro;
bool resultFlag = false;

queue<pair<int, int>> wQ, twQ, dQ, tdQ;

void Input() {
    cin >> N >> M;
    arr.resize(N, vector<char>(M));
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int k = 0; k < M; k++) {
            arr[i][k] = str[k];
            if (str[k] == 'L') {
                originSero = i;
                originGaro = k;
            }
            if (str[k] == '.' || str[k] == 'L') {
                wQ.push({ i, k });
            }
        }
    }
}

void initVisited() {
    visited.assign(N, vector<bool>(M, false));
}

bool isInside(int sero, int garo) {
    return sero >= 0 && sero < N && garo >= 0 && garo < M;
}

void waterBFS() {
    while (!wQ.empty()) {
        int nowSero = wQ.front().first;
        int nowGaro = wQ.front().second;
        wQ.pop();

        for (int i = 0; i < 4; i++) {
            int nextSero = nowSero + dy[i];
            int nextGaro = nowGaro + dx[i];

            if (!isInside(nextSero, nextGaro)) continue;
            if (arr[nextSero][nextGaro] == 'X') {
                arr[nextSero][nextGaro] = '.';
                twQ.push({ nextSero, nextGaro });
            }
        }
    }
}

void duckBFS() {
    while (!dQ.empty()) {
        int nowSero = dQ.front().first;
        int nowGaro = dQ.front().second;
        dQ.pop();

        for (int i = 0; i < 4; i++) {
            int nextSero = nowSero + dy[i];
            int nextGaro = nowGaro + dx[i];

            if (!isInside(nextSero, nextGaro)) continue;
            if (visited[nextSero][nextGaro]) continue;

            visited[nextSero][nextGaro] = true;
            if (arr[nextSero][nextGaro] == 'L') {
                resultFlag = true;
                return;
            }

            if (arr[nextSero][nextGaro] == '.') {
                dQ.push({ nextSero, nextGaro });
            }
            else if (arr[nextSero][nextGaro] == 'X') {
                tdQ.push({ nextSero, nextGaro });
            }
        }
    }
}

void Game_Start() {
    initVisited();
    dQ.push({ originSero, originGaro });
    visited[originSero][originGaro] = true;

    int count = 0;
    while (true) {
        duckBFS();
        if (resultFlag) {
            cout << count << endl;
            return;
        }

        waterBFS();
        wQ = twQ;
        dQ = tdQ;

        while (!twQ.empty()) twQ.pop();
        while (!tdQ.empty()) tdQ.pop();

        count++;
    }
}

int main() {
    Input();
    Game_Start();
    return 0;
}