[BAEKJOON] 16441. 아기돼지와 늑대

Posted on March 10, 2021

문제 :

산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.

고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.

고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.

게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 ‘안전한 곳’이라고 부릅니다. 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

입력 :

첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다.

i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 ’.’ 일 경우 초원, ’+’ 일 경우 빙판, ’#’ 일 경우 산, 그리고 ’W‘는 늑대가 살고 있음을 나타냅니다. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

출력 :

입력으로 주어진 지도를 출력하되 아기돼지가 살 수 있는 초원은 문자 ‘P’로 대체하여 출력합니다.

풀이 :

내가 접근한 방식은 쉽게 말하자면 늑대가 탐색할 수 있는 칸으로 모두 visit 체크해준 후, map배열에서 초원 칸인데 방문하지 않은 칸은 ‘P’ 글자로 바꿔주는 방식이다.

말은 되게 쉬워 보이지만…ㅎ 이문제에서는 몇가지 주의해야할 점이 있다.

우선 빙판이다. 빙판의 경우는 늑대가 걷던 방향으로 계속 미끄러져 가다 산 or 초원 or (나 같은 경우에는 예외 처리로 map배열에서 벗어난 인덱스도 체크함) 일 때 멈추게 된다. 이 부분은 별도로 while문을 만들어 코딩했다.

visit 배열은 한번 방문했는 경우에는 다른 늑대가 방문하더라도 더이상 탐색할 필요가 없다는 것을 잘 고려해주어야 한다. 방문한 곳을 다른 늑대가 왔다고 다시 탐색해주면 당연히 탐색 시간이 더 늘어나겠지??? 어쨌든 본 문제는 빙판을 밟은 경우에 구현을 깔끔하게 해야 코드가 더러워지지 않는 듯 하다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

#define pii pair<int, int>

using namespace std;
vector<pii > wolfvec;
char map[100][100];
bool visit[100][100];
int n, m, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

void bfs(int x, int y) {
    if (visit[x][y]) return;

    queue<pii > q;
    q.push(pii(x, y));
    visit[x][y] = true;

    while (!q.empty()) {
        int curx = q.front().first, cury = q.front().second;
        q.pop();

        for (int k = 0; k < 4; k++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if (cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= m) continue;
            if (map[cmpx][cmpy] == '.' && !visit[cmpx][cmpy]) {
                q.push(pii(cmpx, cmpy));
                visit[cmpx][cmpy] = true;
            } else if (map[cmpx][cmpy] == '+') {
                while (1) {
                    int nextx = cmpx + di[k], nexty = cmpy + dj[k];
                    if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) break;
                    if (map[nextx][nexty] == '#') {
                        if (!visit[cmpx][cmpy]) {
                            q.push(pii(cmpx, cmpy));
                            visit[cmpx][cmpy] = true;
                        }
                        break;
                    }
                    if (map[nextx][nexty] == '.') {
                        if (!visit[nextx][nexty]) {
                            q.push(pii(nextx, nexty));
                            visit[nextx][nexty] = true;
                        }
                        break;
                    }
                    cmpx = nextx;
                    cmpy = nexty;
                }
            }
        }
    }
}

int main() {
    int i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'W') {
                wolfvec.emplace_back(i, j);
                map[i][j] = '.';
            }
        }

    int size = wolfvec.size();
    for (i = 0; i < size; i++)
        bfs(wolfvec[i].first, wolfvec[i].second);
    for (i = 0; i < size; i++)
        map[wolfvec[i].first][wolfvec[i].second] = 'W';

    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (map[i][j] == '.' && !visit[i][j]) cout << 'P';
            else cout << map[i][j];
        }
        cout << '\n';
    }
    return 0;
}

Algorithm

algorithm baekjoon C++