[구름톤 챌린지] 4주차 학습 일기 #2 (20일차) & 후기

 

문제 링크

구름LEVEL

 

 

 

 

문제 설명

 

 

입력 

 

 

출력

 

 

문제 이해

이전에 풀었던 발전기랑 풀이 방식이 굉장히 유사하다.

1. 상하좌우로 같은 알파벳이 있으면 이동하여 다시 상하좌우를 비교한다.

2. 1을 더 이상 상하좌우에 같은 알파벳이 안 나올 때까지 반복한다.(DFS를 사용)

3. 총 반복 횟수 + 1(처음 자리)가 연결 요소의 개수이다.

4. 연결 요소를 저장한 vector의 size를 확인하여 k개 이상이면 해당하는 칸에 알파벳을 점으로 변경해 준다.

5. 1~4까지의 행위가 문제 설명에 있는 작업이며 이를 q번 반복하면 끝난다.

 

 

 

문제 해결

 

1. DFS함수와 연결 요소를 저장할 vector인 save를 만들어주어 연산한다.

    vector<vector<int>> visit(50, vector<int>(50, 0));
    stack<pair<int,int>> s;
    vector<pair<int, int>> save;
    s.push(make_pair(y,x));
    save.push_back(make_pair(y,x));
    visit[y][x] = 1;
    while(!s.empty()){
        int ty = s.top().first;
        int tx = s.top().second;
        s.pop();
        for (int i = 0; i < 4; i++) {
            int px = tx + dx[i];
            int py = ty + dy[i];
            if (px < 0 || px >= n || py < 0 || py >= n ) continue;
            if((visit[py][px] == 0) && (graph[py][px] == c)) {
                s.push(make_pair(py, px));
                save.push_back(make_pair(py, px));
                visit[py][px] = 1;
            }
        }
    }
    if (save.size() >= k) {
        for (int i = 0; i < save.size(); i++) {
            graph[save[i].first][save[i].second] = '.';
        }
    }

 

2. 연결 요소 save의 크기를 확인하여 k개 이상이면 점으로 바꿔준다

    if (save.size() >= k) {
        for (int i = 0; i < save.size(); i++) {
            graph[save[i].first][save[i].second] = '.';
        }
    }

 

3.  1~2를 q번 반복해 준다.

    for (int i = 0; i < q; i++) {
        cin >> y >> x >> c;
        y -= 1;
        x -= 1;
        graph[y][x] = c;
        visit[y][x] = 1;
        dfs(y, x, graph[y][x]);
        for (int j = 0; j < n; j++) {
            fill_n(visit[j], 50, 0);
        }
    }

 

 

문제 후기

처음 코드를 짤 때는 모든 요소의 개수를 확인해 본다고 하여 x, y, c를 입력받을 때마다 모든 graph 위치를 확인해보며 점으로 만들어 줬었는데, 생각해 보니 처음 graph에서 k개 이상인 연결 요소가 없기 때문에 그냥 입력받은 알파벳에 대해서만 연산해 주었으면 됐었다. 

 

이렇게 구름톤 챌린지가 끝이 났다. 문제들이 크게 어렵지도 않으면서, 되게 근본적인 기본기들을 기를 수 있었던 것 같다.

하루씩 늦게 올리는 바람에 블록 보상도 몇 개 빠지고 시작 자체도 3일 차부터 시작한 터라, 블록들을 모두 못채운건 아쉽다.

재미있었고, 특히 그래프에서의 각 이론들을 확실하게 배우고 응용해 볼 수 있었다.

 

전체 코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
char graph[50][50];
int n, k, q;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

void dfs(int y, int x, char c){
    vector<vector<int>> visit(50, vector<int>(50, 0));
    stack<pair<int,int>> s;
    vector<pair<int, int>> save;
    s.push(make_pair(y,x));
    save.push_back(make_pair(y,x));
    visit[y][x] = 1;
    while(!s.empty()){
        int ty = s.top().first;
        int tx = s.top().second;
        s.pop();
        for (int i = 0; i < 4; i++) {
            int px = tx + dx[i];
            int py = ty + dy[i];
            if (px < 0 || px >= n || py < 0 || py >= n ) continue;
            if((visit[py][px] == 0) && (graph[py][px] == c)) {
                s.push(make_pair(py, px));
                save.push_back(make_pair(py, px));
                visit[py][px] = 1;
            }
        }
    }
    if (save.size() >= k) {
        for (int i = 0; i < save.size(); i++) {
            graph[save[i].first][save[i].second] = '.';
        }
    }
}

void pnt() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
        {
            cout << graph[i][j];
        }
        cout << endl;
    }
}

int main(){
    cin >> n >> k >> q;
    for(int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
        {
            cin >> graph[i][j];
        }
    }
    int y, x;
    char c;
    for (int i = 0; i < q; i++) {
        cin >> y >> x >> c;
        y -= 1;
        x -= 1;
        graph[y][x] = c;
        dfs(y, x, graph[y][x]);
    }
    pnt();
}