[C++#2-4] 확산 알고리즘

이번 시간은 내가 생각하는 구현의 마지막 '확산 알고리즘'이다.

회전, 이동, 밀기, 확산까지 전부 스스로 코드를 구현할 수 있다면, 어지간한 구현 문제는 해결할 수 있다고 생각한다.

확산의 정의는 다음과 같다.

확산(擴散)은 액체나 기체에 다른 물질이 섞이고, 그것이 조금씩 번져가다가 마지막에는 일률적인 농도로 바뀌는 현상이다.

확산 알고리즘은 말 그대로 무엇인가 퍼지는 현상을 코드로 구현하는 것이다.

1. 확산 알고리즘

다음과 같이 1차원 맵(배열)에 사람이 있고, 사람이 있는 자리의 양쪽에 사람을 추가로 배치하려고 한다.

다음 문제를 어떻게 해결할 수 있을까?

1-1. 1차원 확산

지난 시간동안 우리는 1차원 맵을 배열로 표현하는 것을 계속 했었다.

지난 시간과 같이 사람을 1, 빈 자리를 0으로 표현하면 아래와 같이 표현할 수 있다.

그리고 우리가 원하는 결과는 배열로 아래와 같을 것이다.

처음에 확산 알고리즘을 구현하려 할 때,

단순하게 조회하면서 1을 추가하면 되지 않을까??

하는 생각을 했었다.

그래서 배열의 0번 index부터 마지막 index까지 조회하면서 1을 추가했더니, 아래와 같은 오류가 발생했다.

조회하면서 넣어준 1의 값이 다음 조회에 간섭되어 배열의 모든 값이 1이 되어버린 것이다....

조회하면서의 간섭을 없애기 위해 맵의 크기와 똑같은 크기의 배열을 하나 더 생성했다.

임의로 이 배열의 이름을 check로 잡았다.

탐색은 arr에서 하면서 check 배열에 사람을 추가하면서 조회를 하는 동안의 간섭을 피할 수 있었다.

탐색의 과정은 아래 그림과 같다.

탐색1

탐색2

탐색3

탐색4

탐색5

최종적으로 탐색을 마쳤을 때 배열은 아래와 같이 된다.

arr배열과 check배열의 각 index들을 더해주면서 우리가 처음 생각했던 결과값을 얻을 수 있었다.

확산을 코드로 구현하면 아래와 같다.

 
int arr[8] = { 0, 1, 0, 0, 0, 1, 0, 0 };
int check[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
for(int i = 0; i < 8; i++){
    if(arr[i] == 1){
        if(i-1 > -1 ) //Map을 벗어날 상황에 대한 예외 처리
            check[i-1] = 1;
        if(i+1 < 8 )  //Map을 벗어날 상황에 대한 예외 처리
            check[i+1] = 1;
    }
}
 
for(int i = 0; i < 8; i++){
    arr[i] += check[i];
}
 

1-2. 2차원 확산

그러면 다음과 같은 2차원 맵에서 사람이 있는 index의 상하좌우에 사람을 추가하고자 한다면 어떻게 할까?

2차원 확산 또한 기본적인 내용은 1차원 확산과 같다.

내용은 1차원 확산과 같으므로 생략하고, 코드로 구현하면 아래와 같다.

 
int arr[3][8] =  { { 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0 } };
int check[3][8]  =  { { 0, 0, 0, 0, 0, 0, 0, 0 },                
                   { 0, 0, 0, 0, 0, 0, 0, 0 },
                   { 0, 0, 0, 0, 0, 0, 0, 0 } };
 
 
for(int i = 0; i < 3; i++){
    for(int j = 0; j < 8; j++){
        if(arr[i][j] == 1){ 
            if(i-1 >= 0) check[i-1][j] = 1;
            if(i+1 < 3) check[i+1][j] = 1;
            if(j-1 >= 0) check[i][j-1] = 1;
            if(j+1 < 8) check [i][j+1] = 1;
        }
    }
}
 
for(int i = 0; i < 3; i++){
    for(int j = 0; j < 8; j++){
        arr[i][j] += check[i][j];
    }
}