[C++] 17999번 Maze Connect

 

 

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

---

 

25/09/30

 

 

어떻게 해야할 지는 금방 보이는 문제이지만, 어떻게 구현해야 할지가 큰 고민인 문제다.

---

 

문제 접근 방식:

 

 

문제가 영어로 되어있긴 하지만, 요약하자면, 대각선 모양으로 갇혀있는 방의 개수를 세어주면 되는 문제다.

 

이때 방은 외부와 연결되어있지 않은, 닫힌 한 구역을 의미한다.

 

그러면 자연스럽게 "그냥 BFS 쓰면 되겠네"하는 아이디어가 떠오를 것이다.

 

근데 문제는 입력 형식이다. 어떻게 BFS를 진행할 것인가가 결국 문제인데...

 

 

입력 형식이 일반적인 격자 형태로 주어지는 것이 아니라 격자가 45도 회전된 모양으로 주어지기 때문에 BFS를 어떻게 처리해야할 지가 고민이다.

 

같은 칸 이어도, 그 칸이 실제로는 하나의 칸을 나타내는 것이 아니라 45도 회전 된 벽을 나타내기 때문에 2개의 구역에 걸쳐져 있기 때문이다.

 

여기서 3차원 BFS의 아이디어를 떠올렸다.

 

visited배열의 정의는 다음과 같다.

 

$$\text{visited}[d][r][c] \ = \ r행 \ c열의 \ 칸을 \ 방향 \ d로 \ 도착했을 \ 때의 \ 방문 \ 여부$$

 

우측 하단을 향하는 대각선 칸이 있다면, 해당 대각선 칸을 위에서 도착했다면 오른쪽으로 향해야 한다. 마찬가지로 해당 칸을 오른쪽에서 도착했다면 아래로 향해야 한다.

 

반대 방향도 마찬가지이고, 우측 상단을 향하는 대각선 칸도 마찬가지로 이전 방향에 따라 현재 어느 방향으로 향해야 하는지를 1대 1 대응 시켜줄 수 있다.

 

아래 코드를 참고하면 확인할 수 있지만, 해당 1대 1 대응을 mapping이라는 이름으로 하드코딩 해두었다.

 

해당 배열의 인덱스는 이전 방향, 그리고 현재 방향은 그 때의 값이 되도록 설정해두었다.

 

빈칸일 때는 4방향 모두 퍼져나갈 수 있으므로, 그때는 4방향으로 퍼지게끔 BFS를 진행해두었다.

 

 

현재 구역이 외부와 연결되어있는지의 여부는 현재 구역에서 BFS를 돌렸을 때 경계를 벗어났는지의 여부를 통해 확인할 수 있다.

 

 

이를 통해 방의 개수를 세어줄 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 17999번 Maze Connect
// BFS, 구현
/*
접근 방법:
visited[r][c][i] = r, c위치를 i방향으로 도착하였을 때...
*/
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int visited[1000][1000][4] = {0};
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
char MAP[1000][1000];
int R, C;
int mapping[2][4] = {
    {3, 2, 1, 0},
    {2, 3, 0, 1}
};

bool inb(int r, int c){
    return (0 <= r) && (r < R) && (0 <= c) && (c < C);
}

int bfs(int r, int c){
    queue<pair<pair<int, int>, int>> bfs_q;
    int check = 1;
    visited[r][c][0] = 1; visited[r][c][2] = 1;
    bfs_q.push({{r, c}, 0}); bfs_q.push({{r, c}, 2});
    while (!bfs_q.empty()){
        pair<int, int> pos = bfs_q.front().first;
        int d = bfs_q.front().second;
        bfs_q.pop();
        int rr = pos.first, cc = pos.second;
        if (MAP[rr][cc] == '/'){
            int nd = mapping[0][d];
            int nr = rr+dr[nd], nc = cc+dc[nd];
            if (inb(nr, nc)){
                if (visited[nr][nc][nd] == 0){
                    visited[nr][nc][nd] = 1;
                    bfs_q.push({{nr, nc}, nd});
                }
            } else {
                check = 0;
            }
        }
        else if (MAP[rr][cc] == '\\'){
            int nd = mapping[1][d];
            int nr = rr+dr[nd], nc = cc+dc[nd];
            if (inb(nr, nc)){
                if (visited[nr][nc][nd] == 0){
                    visited[nr][nc][nd] = 1;
                    bfs_q.push({{nr, nc}, nd});
                }
            } else {
                check = 0;
            }
        }
        else{
            for (int i = 0; i < 4; ++i){
                int nr = rr+dr[i], nc = cc+dc[i];
                if (inb(nr, nc)){
                    if (visited[nr][nc][i] == 0){
                        visited[nr][nc][i] = 1;
                        bfs_q.push({{nr, nc}, i});
                    }
                } else {
                    check = 0;
                }
            }
        }
    }
    return check;
}

int main(void){
    fastio;
    // init
    cin >> R >> C;
    for (int r = 0; r < R; ++r){
        for (int c = 0; c < C; ++c){
            cin >> MAP[r][c];
        }
    }
    // BFS
    int ans = 0;
    for (int r = 0; r < R; ++r){
        for (int c = 0; c < C; ++c){
            if ((MAP[r][c] == '/') && visited[r][c][0] == 0 && visited[r][c][2] == 0){
                ans += bfs(r, c);
            }
        }
    }
    cout << ans << endl;
    return 0;
}