2933번 미네랄, 18500번 미네랄 2

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

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

bfs dfs sw역량테스트 삼성 코딩테스트 코테 코딩 필수 복습 추천 구현 simulation boj 백준 시뮬레이션 연결요소의 개수

2933번(미네랄)과 18500번(미네랄2)은 거의 같은 문제라고 할 수 있다.(사실 정확한 문제 구분은 모르겠음.)

핵심은 아래 3가지인 것 같다.

1. DFS를 이용한 연결 요소의 활용(Group을 지을 줄 아는가? 즉, Grouping(그루핑))

2. BFS를 통한 각 그룹에서 다른 그룹 또는 맨 밑까지의 거리들 중의 최솟값

3. x를 아래로 이동시키기(구현력) → 나는 임시배열(t)을 활용

참고로 행, 열을 (0 ~ R - 1, 0 ~ C - 1)표현하였기 때문에 입력으로 주어지는 막대를 던지는 높이는 R - stick이라고 할 수 있다.

예시)

왼쪽이 입력으로 주어지는 막대의 높이

오른쪽이 그 높이를 내가 생각하는 배열에서의 행(위치)

8 → 0

7 → 1

6 → 2

5 → 3

4 → 4

3 → 5

2 → 6

1 → 7

temp 배열은 각 x를 같은 그룹끼리는 같은 번호(gn)를 표시한 것이다.

나머지는 코드 안의 주석을 참고.

answer.cpp

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 103
 
int R, C, n;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
char m[Max][Max];
bool visit[Max][Max]; // 방문 여부
vector<int> stick; // 막대기 높이
 
// 한 그룹(num)에서 다른 그룹(!= num) 또는 맨 밑으로 이동할 수 있는 거리들 중 최솟값
int bfs(int num, int temp[][Max], queue<pair<int, int> > &q)
{
    int ret = 0; // 반환할 거리
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            // 마지막에 도달했으면 return
            if (r == R - 1) {
                return ret;
            }
            // 다음 칸이 'x'이면서 같은 그룹이 아니라면(temp의 숫자가 달라야 한다.) return
            else if (r + 1 < R && m[r + 1][c] == 'x' && temp[r + 1][c] != num) {
                return ret;
            }
 
            // 아래로만 이동하기 때문에 따로 방문 처리가 필요 없다.
            if (r + 1 < R && temp[r + 1][c] != num) {
                q.push({ r + 1, c });
            }
        }
 
        ++ret;
    }
 
    return ret;
}
 
void dfs(int r, int c, int gn, int temp[][Max], vector<pair<int, int> > &vt)
{
    visit[r][c] = true; // 방문 처리
    temp[r][c] = gn; // x의 위치를 고려하여, Group을 기록한다. 같은 그룹이면 같은 gn(그룹 번호)이다.
    vt.push_back({ r, c }); // 같은 그룹끼리 좌표를 활용해야하기 때문에 vt에 담아야 한다.
 
    for (int i = 0; i < 4; i++) {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || m[y][x] == '.') {
            continue;
        }
 
        dfs(y, x, gn, temp, vt);
    }
}
 
void chk()
{
    memset(visit, false, sizeof(visit));
 
    int cnt = 0, temp[Max][Max] = { 0 };
    vector<vector<pair<int, int> > > v;
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            
            vector<pair<int, int> > vt;
    
            // 연결 요소
            if (!visit[i][j] && m[i][j] == 'x') {
                dfs(i, j, cnt + 1, temp, vt);
                ++cnt;
            }
 
            // 비어있지 않으면 x가 있다는 뜻이므로, v에 담는다.
            if (!vt.empty()) {
                v.push_back(vt);
            }
        }
    }
 
    int num = 1;
    for (auto i : v) {
        queue<pair<int, int> > q;
 
        // 각 그룹에 따른 좌표들을 queue에 담는다.
        for (auto j : i) {
            q.push({ j.first, j.second });
        }
 
        int dist = bfs(num, temp, q);
 
        // 0이 아니라는 것은 아래로 떨어질 위치가 있다는 것이다.
        if (dist != 0) {
 
            // 임시 배열
            char t[Max][Max];
 
            for (auto j : i) {
                // 새로운 위치(행 + dist)에 원래(행)의 값을 넣는다.
                t[j.first + dist][j.second] = m[j.first][j.second];
                m[j.first][j.second] = '.'; // 원래 좌표는 없앤다.
            }
 
            for (auto j : i) {
                // 새로운 위치를 활용
                m[j.first + dist][j.second] = t[j.first + dist][j.second];
            }
 
            // 둘 이상의 클러스터가 떨어질 일은 없기 때문에 break가 가능하다.
            break;
        }
 
        ++num;
    }
}
 
void simulation()
{
    for (int i = 0; i < n; i++) {
        int r =  R - stick[i];
        if (i % 2) {
            // 홀수(오른쪽에서 왼쪽으로 던짐)
            for (int j = C - 1; j >= 0; j--) {
                if (m[r][j] == 'x') {
                    m[r][j] = '.';
                    chk(); // 하나 씩 없어질 때마다 검사
                    break; // 1개만 없어진다.(문제 조건)
                }
            }
        }
        else {
            // 짝수(왼쪽에서 오른쪽으로 던짐)
            for (int j = 0; j < C; j++) {
                if (m[r][j] == 'x') {
                    m[r][j] = '.';
                    chk(); // 하나 씩 없어질 때마다 검사
                    break; // 1개만 없어진다.(문제 조건)
                }
            }
        }
    }
 
    // 정답 출력
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%c", m[i][j]);
        }
        printf("\n");
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
        }
    }
 
    cin >> n;
 
    stick.assign(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> stick[i];
    }
 
    simulation();
 
    return 0;
}