문제 링크

삼성 코딩테스트 기출 문제: 마법의 숲 탐색 - 코드트리

주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.

코드트리

문제 설명

r*c의 격자이고, 정령(골렘)들은 북쪽을 통해서 들어옴. K명의 정령들은 골렘을 타고 숲을 탐색하는데, 골렘은 십자 모양의 구조를 가지고 있고, 중앙 칸을 포함해 5칸을 차지함. 중앙을 제외한 나머지 1칸은 출구로, 골렘에서 내릴 때에는 반드시 정해진 출구를 통해서만 내릴 수 있음. i번째로 숲을 탐색하는 골렘은 숲의 가장 북쪽에서 시작해 골렘의 중앙의 c_i열이 되도록 하는 위치에서 내려옴. 초기 골렘의 출구는 d_i방향에 위치하고 있음.

골렘은 숲을 탐색하기 위해 다음과 같은 우선순위로 이동하는데, 더이상 움직이지 못할 때까지 다음 과정을 반복함.

1. 남쪽으로 한 칸 내려감
2. (1)이 안된다면, 서쪽 방향으로 회전하면서 내려감
3. (2)가 안된다면, 동쪽 방향으로 회전하면서 내려감

더이상 움직일 수 없다면, 정령은 갈 수 있는 칸 중 가장 남쪽의 칸으로 이동하고 완전히 종료함.

해결 방법

1. 아래로 내려갈 수 있는 공간이 있다면, 내려가기
2. 그렇지 않다면 왼쪽으로 내려갈 수 있는 공간이 있다면 내려가고 골렘의 좌표값과 출구 값 변경
3. 그렇지 않다면 오른쪽으로 내려갈 수 있는 공간이 있다면 내려가고 골렘의 좌표값과 출구 값 변경
4. 그것도 안된다면 골렘은 더이상 내려갈 수 없음.

골렘 움직이기

for (r = 0;r <= n;r++) {
    int c = gol[g].c;
    if (in_bound_r(r + 2) && in_bound_c(c - 1) && in_bound_c(c + 1) && arr[r + 1][c - 1] == 0 && arr[r + 1][c + 1] == 0 && arr[r + 2][c] == 0) {
        continue;
    }
    else {
        if (in_bound_r(r - 1) && in_bound_r(r + 2) && in_bound_c(c - 2) && arr[r - 1][c - 1] == 0&& arr[r][c - 2] == 0&& arr[r + 1][c - 1] == 0&& arr[r + 1][c - 2] == 0 && arr[r + 2][c - 1] == 0) {
            gol[g].c = gol[g].c - 1;
            gol[g].d = gol[g].d == 0 ? 3 : gol[g].d - 1;

      }
        else if (in_bound_r(r - 1) && in_bound_r(r + 2) && in_bound_c(c + 2) && arr[r - 1][c + 1] == 0&& arr[r][c + 2] == 0&& arr[r + 1][c + 1] == 0&& arr[r + 1][c + 2] == 0&& arr[r + 2][c + 1] == 0) {
            gol[g].c = gol[g].c + 1;
            gol[g].d = (gol[g].d + 1) % 4;
        }
        else {
            break;
        }
    }
}

골렘의 상단이 들어가지 못했다면, 배열을 모두 백지상태로 만들고 해당 골렘의 턴 종료.

if (r-1 <= 2) {
    // 몸이 들어가지 못한 상태
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            arr[i][j] = 0;
        }
    }
    return 0;
}

출구를 기준으로 BFS를 돌리고, 도달할 수 있는 값 중 가장 행이 큰 위치를 반환함.

queue<pair<int, int>> que;
int d = gol[g].d;
if (d == 0) {
    arr[r - 1][c] = -g;
    que.push({ r - 1,c });
}
else if (d == 1) {
    arr[r][c + 1] = -g;
    que.push({ r,c + 1 });
}
else if (d == 2) {
    arr[r + 1][c] = -g;
    que.push({ r + 1,c });
}
else {
    arr[r][c - 1] = -g;
    que.push({ r,c - 1 });
}

int cx, cy, nx, ny;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
while (!que.empty()) {
    tie(cx, cy) = que.front();
    que.pop();
    for (int i = 0;i < 4;i++) {
        nx = cx + dx[i], ny = cy + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visited[nx][ny] || arr[nx][ny] == 0) continue;
        if (arr[cx][cy] > 0 && abs(arr[nx][ny]) != abs(arr[cx][cy])) continue;
        visited[nx][ny] = 1;
        que.push({ nx,ny });
    }
}

for (int i = n - 1;i >= 0;i--) {
for (int j = 0;j < m;j++) {
    if (visited[i][j] == 1) {
        return i - 2;
    }
}

전체 코드

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

typedef struct {
    int c, d; // 열, 방향 (북,동,남,서)
}_gol;

int n, m, k;
_gol gol[1002];
int arr[73][73];
int visited[73][73];

void input() {
    cin >> n >> m >> k;

    int c, d;
    for (int i = 1;i <= k;i++) {
        cin >> c >> d;
        gol[i].c = c - 1;
        gol[i].d = d;
    }

    n += 3;
}

void print_arr() {
    cout << "print_arr:\\n";
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (arr[i][j] < 0) cout << "# ";
            else cout << arr[i][j] << " ";
        }
        cout << "\\n";
    }
    cout << "\\n";
}

bool in_bound_r(int r) {
    if (r < 0 || r >= n) return false;
    else return true;
}

bool in_bound_c(int c) {
    if (c < 0 || c >= m) return false;
    return true;
}

int golem_move(int g) {
    int r;
    for (r = 0;r <= n;r++) {
        int c = gol[g].c;
        // 1. 남쪽으로 내려갈 수 있는지
        // arr[r+1][c-1] && arr[r+1][c+1] && arr[r+2][c]
        // 2. 왼쪽으로 회전하고 내려갈 수 있는지
        // arr[r-1][c-1] && arr[r][c-2] && arr[r+1][c-1]
        // arr[r+1][c-2] && arr[r+2][c-1]
        // 3. 오른쪽으로 회전하고 내려갈 수 있는지
        // arr[r-1][c+1] && arr[r][c+2] && arr[r+1][c+1]
        // arr[r+1][c+2] && arr[r+2][c+1]
        if (in_bound_r(r + 2) && in_bound_c(c - 1) && in_bound_c(c + 1) && arr[r + 1][c - 1] == 0 && arr[r + 1][c + 1] == 0 && arr[r + 2][c] == 0) {
            continue;
        }
        else if (r == 0) {
            if (in_bound_r(r + 2) && in_bound_c(c - 2) && arr[r][c - 2] == 0 && arr[r + 1][c - 1] == 0 && arr[r + 1][c - 2] == 0 && arr[r + 2][c - 1] == 0) {
                gol[g].c = gol[g].c - 1;
                gol[g].d = gol[g].d == 0 ? 3 : gol[g].d - 1;
            }
            else if (in_bound_r(r + 2) && in_bound_c(c + 2) && arr[r][c + 2] == 0 && arr[r + 1][c + 1] == 0 && arr[r + 1][c + 2] == 0 && arr[r + 2][c + 1] == 0) {
                gol[g].c = gol[g].c + 1;
                gol[g].d = (gol[g].d + 1) % 4;
            }
            else {
                break;
            }
        }
        else {
            if (in_bound_r(r - 1) && in_bound_r(r + 2) && in_bound_c(c - 2) && arr[r - 1][c - 1] == 0&& arr[r][c - 2] == 0&& arr[r + 1][c - 1] == 0&& arr[r + 1][c - 2] == 0 && arr[r + 2][c - 1] == 0) {
                gol[g].c = gol[g].c - 1;
                gol[g].d = gol[g].d == 0 ? 3 : gol[g].d - 1;

            }
            else if (in_bound_r(r - 1) && in_bound_r(r + 2) && in_bound_c(c + 2) && arr[r - 1][c + 1] == 0&& arr[r][c + 2] == 0&& arr[r + 1][c + 1] == 0&& arr[r + 1][c + 2] == 0&& arr[r + 2][c + 1] == 0) {
                gol[g].c = gol[g].c + 1;
                gol[g].d = (gol[g].d + 1) % 4;
            }
            else {
                break;
            }
        }
    }
    if (r-1 <= 2) {
        // 몸이 들어가지 못한 상태
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                arr[i][j] = 0;
            }
        }
        return 0;
    }

    memset(visited, 0, sizeof(visited));

    int c = gol[g].c;
    arr[r][c] = g;
    arr[r - 1][c] = g;
    arr[r + 1][c] = g;
    arr[r][c - 1] = g;
    arr[r][c + 1] = g;

    memset(visited, 0, sizeof(visited));
    visited[r][c] = 1;
    visited[r - 1][c] = 1;
    visited[r + 1][c] = 1;
    visited[r][c - 1] = 1;
    visited[r][c + 1] = 1;

    // 북동남서
    queue<pair<int, int>> que;
    int d = gol[g].d;
    if (d == 0) {
        arr[r - 1][c] = -g;
        que.push({ r - 1,c });
    }
    else if (d == 1) {
        arr[r][c + 1] = -g;
        que.push({ r,c + 1 });
    }
    else if (d == 2) {
        arr[r + 1][c] = -g;
        que.push({ r + 1,c });
    }
    else {
        arr[r][c - 1] = -g;
        que.push({ r,c - 1 });
    }

    int cx, cy, nx, ny;
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    while (!que.empty()) {
        tie(cx, cy) = que.front();
        que.pop();
        for (int i = 0;i < 4;i++) {
            nx = cx + dx[i], ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || arr[nx][ny] == 0) continue;
            if (arr[cx][cy] > 0 && abs(arr[nx][ny]) != abs(arr[cx][cy])) continue;
            visited[nx][ny] = 1;
            que.push({ nx,ny });
        }
    }

    /*
    cout << "visited:\\n";
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cout << visited[i][j] << " ";
        }
        cout << "\\n";
    }
    */

    for (int i = n - 1;i >= 0;i--) {
        for (int j = 0;j < m;j++) {
            if (visited[i][j] == 1) {
                return i - 2;
            }
        }
    }
}

void solve() {
    int result = 0;
    for (int g = 1;g <= k;g++) {
        result += golem_move(g);
//        print_arr();
    }
    cout << result;
}

void init() {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            arr[i][j] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("sample_input.txt", "r", stdin);

    input();
    init();
    solve();

    return 0;
}