By 정우석 in Problem Solving —

고대 문명 유적 탐사 [2024-상반기 오전 1번 문제]

문제 링크

삼성 코딩테스트 기출 문제: 고대 문명 유적 탐사 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
코드트리

문제 설명

5*5 형태의 배열이 있음. 해당 배열에는 1-7의 값이 있음.

  1. 3*3의 격자 선택 및 회전5*5 형태의 배열 내에서 3*3의 격자를 선택해야 함. 해당 격자를 90도, 180도, 270도 회전이 가능함. 격자 선택의 순서는 다음과 같음 : (1) 유물 1차 획득 최대화 → (2) 회전한 각도가 가장 작은 방법 → (3) 열이 가장 작은 구간, 열이 같다면 행이 가장 적은 구간
  2. 유물 획득회전 후, 3개 이상 연결되어 있는 값들을 제거하고, 제거한 값들을 유적 벽면에 적혀있는 숫자들을 집어 넣음. 유적 벽면에 적는 순서는 다음과 같음 : (1) 열 번호가 가장 작은 순 → (2) 행 번호가 가장 큰 순
  3. 유물 연쇄 획득유물이 새로 생겨난 후에, 3개 이상 연결되어 있는 값들이 없을 때까지 획득 및 제거를 반복함.

탐사 진행 - 유물 연쇄 획득을 K번의 턴에 걸쳐 진행함.

해결 방법

유물 획득회전한 배열을 기반으로, 유물 획득 - 유물 생성을 반복해줌. 해당 결과에서 얻는 값들을 cur_cnt에 저장해줌.

        while (true) {
            int cur_val = get_treasure();
            cur_cnt += cur_val;
            if (cur_val == 0) break;
            write_val();
        }

유물 획득 코드. 1번의 chk_treasure과 로직이 비슷함.

int get_treasure() {
    memset(visited, 0, sizeof(visited));
    int cx, cy, nx, ny;
    int ret = 0;
    for (int x = 0;x < 5;x++) {
        for (int y = 0;y < 5;y++) {
            if (visited[x][y]) continue;
            queue<pair<int, int>> que;
            vector<pair<int, int>> pop_list;
            que.push({ x,y });
            pop_list.push_back({ x,y });
            
            visited[x][y] = 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 >= 5 || ny >= 5) continue;
                    if (visited[nx][ny]) continue;
                    if (arr[cx][cy] != arr[nx][ny]) continue;
                    visited[nx][ny] = 1;
                    que.push({ nx,ny });
                    pop_list.push_back({ nx,ny });
                }
            }
            if (pop_list.size() >= 3) {
                ret += pop_list.size();
                for (int i = 0;i < pop_list.size();i++) {
                    arr[pop_list[i].first][pop_list[i].second] = 0;
                }
            }
        }
    }

    return ret;
}

유물 작성

void write_val() {
    for (int i = 0;i < 5;i++) {
        for (int j = 4;j >= 0;j--) {
            if (arr[j][i] == 0) {
                arr[j][i] = wait_list[list_cur];
                list_cur++;
            }
        }
    }
}

3*3 격자 선택 및 회전문제 설명에는 중간을 골랐으나, 나는 좌측 좌상단을 기준으로 골랐음. 좌측 좌상단을 고르고, 각각 90도, 180도, 270도의 회전 결과를 chk[x][y][t]에 넣어줌.

  memset(chk, 0, sizeof(chk));
  for (int i = 0;i < 3;i++) {
      for (int j = 0;j < 3;j++) {
          get_val(i, j);
          set_arr();
      }
  }
  
  ...
  
  void get_val(int x, int y) {
    // 1. x ... x+2, y ... y+2를 r번 회전
    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            tmp_arr[i][j] = arr[i + x][j + y];
        }
    }

    for (int t = 0;t < 3;t++) {
        rotate();

        for (int i = 0;i < 3;i++) {
            for (int j = 0;j < 3;j++) {
                arr[i + x][j + y] = tmp_arr[i][j];
            }
        }

        chk[x][y][t] = chk_treasure();
    }

    return;
}

회전한 배열에서 얻을 수 있는 값들을 저장하는 함수. BFS를 사용하였음.

// chk 배열에 1차 획득의 결과를 저장 (get_val 보조)
int chk_treasure() {
    memset(visited, 0, sizeof(visited));    
    int cx, cy, nx, ny;
    int ret = 0;

    for (int x = 0;x < 5;x++) {
        for (int y = 0;y < 5;y++) {
            if (visited[x][y]) continue;
            int cnt = 1;
            queue<pair<int, int>> que;
            que.push({ x,y });
            visited[x][y] = 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 >= 5 || ny >= 5) continue;
                    if (visited[nx][ny]) continue;
                    if (arr[cx][cy] != arr[nx][ny]) continue;                    
                    visited[nx][ny] = 1;
                    que.push({ nx,ny });
                    cnt++;
                }
            }
            if (cnt >= 3) ret += cnt;
        }
    }

    return ret;
}

전체 코드

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

int k, m;

int org[6][6];
int arr[6][6];
int wait_list[301];
int list_cur = 0;

int chk[4][4][3];
int tmp_arr[3][3];

// 입력
void input() {
    cin >> k >> m;

    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            cin >> arr[i][j];
            org[i][j] = arr[i][j];
        }
    }

    for (int i = 0;i < m;i++) {
        cin >> wait_list[i] ;
    }

}

// arr를 org으로 원상복구
void set_arr() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            arr[i][j] = org[i][j];
        }
    }
}

// 회전
void rotate() {
    int ttmp[3][3];

    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            ttmp[i][j] = tmp_arr[3 - j - 1][i];
        }
    }

    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            tmp_arr[i][j] = ttmp[i][j];
        }
    }

}

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

// chk 배열에 1차 획득의 결과를 저장 (get_val 보조)
int chk_treasure() {
    memset(visited, 0, sizeof(visited));    
    int cx, cy, nx, ny;
    int ret = 0;

    for (int x = 0;x < 5;x++) {
        for (int y = 0;y < 5;y++) {
            if (visited[x][y]) continue;
            int cnt = 1;
            queue<pair<int, int>> que;
            que.push({ x,y });
            visited[x][y] = 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 >= 5 || ny >= 5) continue;
                    if (visited[nx][ny]) continue;
                    if (arr[cx][cy] != arr[nx][ny]) continue;                    
                    visited[nx][ny] = 1;
                    que.push({ nx,ny });
                    cnt++;
                }
            }
            if (cnt >= 3) ret += cnt;
        }
    }

    return ret;
}

// x,y위치의 배열을 회전 및 결과 넣어주기
void get_val(int x, int y) {
    // 1. x ... x+2, y ... y+2를 r번 회전
    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            tmp_arr[i][j] = arr[i + x][j + y];
        }
    }

    for (int t = 0;t < 3;t++) {
        rotate();

        for (int i = 0;i < 3;i++) {
            for (int j = 0;j < 3;j++) {
                arr[i + x][j + y] = tmp_arr[i][j];
            }
        }

        chk[x][y][t] = chk_treasure();
    }

    return;
}

// tx, ty, tr에 회전, 인덱스저장
void rotate_arr() {
    memset(chk, 0, sizeof(chk));
    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            get_val(i, j);
            set_arr();
        }
    }

    int val = -1;
    // 획득 - 각도 - 열 - 행
    int tr, tx, ty;
    for (int r =0;r < 3;r++) {
        for (int i = 0;i < 3;i++) {
            for (int j = 0;j < 3;j++) {
                if (chk[j][i][r] > val) {
                    val = chk[j][i][r];
                    tx = j, ty = i, tr = r;
                }
            }
        }
    }

    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            tmp_arr[i][j] = arr[i + tx][j + ty];
        }
    }

    for (int t = 0;t <= tr;t++) {
        rotate();

        for (int i = 0;i < 3;i++) {
            for (int j = 0;j < 3;j++) {
                arr[i + tx][j + ty] = tmp_arr[i][j];
            }
        }
    }
}

int get_treasure() {
    memset(visited, 0, sizeof(visited));
    int cx, cy, nx, ny;
    int ret = 0;
    for (int x = 0;x < 5;x++) {
        for (int y = 0;y < 5;y++) {
            if (visited[x][y]) continue;
            queue<pair<int, int>> que;
            vector<pair<int, int>> pop_list;
            que.push({ x,y });
            pop_list.push_back({ x,y });
            
            visited[x][y] = 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 >= 5 || ny >= 5) continue;
                    if (visited[nx][ny]) continue;
                    if (arr[cx][cy] != arr[nx][ny]) continue;
                    visited[nx][ny] = 1;
                    que.push({ nx,ny });
                    pop_list.push_back({ nx,ny });
                }
            }
            if (pop_list.size() >= 3) {
                ret += pop_list.size();
                for (int i = 0;i < pop_list.size();i++) {
                    arr[pop_list[i].first][pop_list[i].second] = 0;
                }
            }
        }
    }

    return ret;
}

void print_arr() {
    cout << "print_arr\\n";

    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\\n";
    }
}

void write_val() {
    for (int i = 0;i < 5;i++) {
        for (int j = 4;j >= 0;j--) {
            if (arr[j][i] == 0) {
                arr[j][i] = wait_list[list_cur];
                list_cur++;
            }
        }
    }
}

void solve() {
    for (int i = 0;i < k;i++) {
        int cur_cnt = 0;
        rotate_arr();
        while (true) {
            int cur_val = get_treasure();
            cur_cnt += cur_val;
            if (cur_val == 0) break;
            write_val();
        }
        if (cur_cnt == 0) break;
        cout << cur_cnt << " ";
        
        for (int x = 0;x < 5;x++) {
            for (int y = 0;y < 5;y++) {
                org[x][y] = arr[x][y];
            }
        }
    }
}

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

    input();
    solve();
    return 0;
}
Previous

미지의 공간 탈출 [2024-하반기 오전 1번 문제]

 Next

마법의 숲 탐색 [2024-상반기 오후 1번 문제]

You might also like...