[코드트리] 1차원 바람 C++

문제

https://www.codetree.ai/missions/2/problems/The-1D-wind-blows?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획세우기

1. vector<pair<int, char>> wind에 불어오는 바람들에 대한 전파가 담겨 있다.

2. wind[i].first 번째 줄을 wind[i].second 방향으로 shift

3. wind[i].first+1, wind[i].first-1번째 줄을 확인해서 전파되는 줄을 propagatedWind에 push_back()한다.

4. propagatedWind에서 값을 하나 빼서 해당 방향으로 shift 전파가 일어나는지 propagation() 체크해서 propagatedWind에 push_back()

5. propagatedWind가 빌 때까지 반복

 

풀이(통과한 코드)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> //memset

using namespace std;

int n, m, q;
int building[101][101]; // N*M 행렬 모양의 건물
int visited[101]; // 방문한 행을 체크하는 배열
vector<pair<int, char>> wind;
vector<pair<int, char>> propagatedWind;

void Propagation(int row, char dir){
    if (dir=='L') dir ='R';
    else dir='L';

    // 중복으로 들어가면 안 되니까
    bool upSignal =false, downSignal = false;
    for(int i=0; i<m; i++){
        if(row+1<n && building[row][i]==building[row+1][i])
            upSignal=true;
        if(row-1>=0 && building[row][i]==building[row-1][i])
            downSignal=true;
    }

    if(upSignal && visited[row+1]==0) propagatedWind.push_back({row+1, dir});
    if(downSignal && visited[row-1]==0) propagatedWind.push_back({row-1, dir});
}


void ShiftArr(int row, char dir){
    if(dir=='L'){
        int lastElement = building[row][m-1];
        for(int i=m-1; i>0; i--){
            building[row][i]= building[row][i-1];
        }
        building[row][0] = lastElement;
    }
    else{
        int firstElement = building[row][0];
        for(int i=0; i<m-1; i++){
            building[row][i]= building[row][i+1];
        }
        building[row][m-1] = firstElement;
    }
}

void WindStart(){
    for(int i=0; i<wind.size(); i++){
    	memset(visited, 0, sizeof(int)*n);

        int row = wind[i].first;
        char dir = wind[i].second;
        ShiftArr(row, dir); // 첫 바람
        visited[row] = 1;
        Propagation(row, dir); // 전파 시키기
        //for(int i=0; i<propagatedWind.size();i++){
        //    cout << propagatedWind[i].first << " " << propagatedWind[i].second << '\n';
        //}
        while(!propagatedWind.empty()){
            row = propagatedWind.back().first;
            dir = propagatedWind.back().second;
            propagatedWind.pop_back();
            ShiftArr(row, dir);
            visited[row]=1;
            Propagation(row, dir);
        }
    }
}

void GetInput(){
    cin >> n >> m >> q;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> building[i][j];
        }
    }
    for (int i=0; i<q; i++){
        int x;
        char dir;
        cin >> x >> dir;
        wind.push_back({--x, dir}); // 1<=x<=n이기 때문에 1을 뺀 후 벡터에 넣어줌
    }
}

void PrintArr(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << building[i][j] << " ";
        }
        cout <<'\n';
    }
}

int main() {
    GetInput();
    
    WindStart();

    PrintArr();
    return 0;
}

 

 

실수1. visited배열 없이 코드를 짰었다

처음에 visited 배열 없이 코드를 짰는데, 아래 예제에서 시간 초과가 났다.

6 5 1
1 5 6 7 3
5 3 2 5 4
6 4 5 2 5
2 6 1 0 5
5 1 2 1 6
4 2 5 2 8
3 L

시간 초과가 날 정도로 복잡한 코드가 아니라고 생각했기 때문에 while(!propagatedWind.empty()) 이 부분이 유력한 범인이라고 생각이 됐다. 손으로 직접 코드가 어떻게 진행되는지 살펴봤다.

1. wind에 {2, L}이 push_back()
2. propagatedWind = {{3, R}, {1, R}}
3. propagatedWind.back() = {1, R}을 빼서 ShiftArr, Propagation(1, R)
4. propagatedWind = {{3, R}}
5. propagatedWind.back() = {3, R}을 빼서 ShiftArr, Propagation(3, R)
   1. propagatedWind.push_back({2, L}); // 이 줄은 이미 바람이 불었던 곳이므로 다시 가면 안 됨! 여기가 문제
   2. propagatedWind.push_back({4, L});

 

처음에는 UpPropagation(), DownPropagation()으로 나눌까 생각했는데, 이 방법보다 좋은 방법이 있을 것 같았다.

재귀를 쓸까?? 라는 생각이 들었다가 어 그냥 지금 코드에 바람 불었던 행만 체크해주면 되지 않나? 라는 생각이 들었다.

그래서 visited 배열을 추가하니 주어진 위의 예제를 통과할 수 있었다.

 

 

실수2. memset(visited, 0, n);

예제1은 통과를 하는데, 예제2는 통과를 못하길래 왜지? 하고 print를 여러군데 찍은 결과 2번째 wind부터 전파가 잘 안 되는 문제가 보였다. 왜인가 찾는데 조금 시간이 걸렸는데, 문제는 memset()에 있었다.

 

visited 배열을 찍어보니 처음에는 0 0 0이 출력됐는데, 두 번째에는 0 1 1이 출력됐다.

 

memset(배열이름, 초기화 할 값(보통 -1, 0, 1), 배열의 크기)

 

위와 같이 memset의 사용법을 기억하고 있었던 터라 문제가 생긴 것 같다.

 

void* memset(void* ptr, int value, size_t num);

 

memset(visited, 0, n)는 "visited 배열을 n 바이트만큼 0으로 바꿔"라는 의미이다.

memset(visited, 0, sizeof(int)*n) 이건 "visited 배열을 n개의 int 크기(n*4 byte) 만큼 0으로 바꿔"라는 의미이다.

 

즉, memset(visited, 0, n)이라고 했을 때, 배열 전체가 초기화 되지 않기 때문에 문제가 발생한 것이다!

 

 

https://coding-factory.tistory.com/673

[C언어/C++] 메모리 초기화 memset 함수 사용법 & 예제