C언어 코딩도장 38.8 지뢰찾기 문제

별거 아닌 것처럼 보였지만 다양한 개념들을 정확하게 알고 있어야 풀 수 있는 문제여서 생각보다 복잡하고 어려웠다.

문제에 "이 문제는 지금까지 심사문제 중에서 가장 어렵습니다. 처음 풀어보는 경우 대략 두 시간은 걸립니다. 시간을 두고 천천히 고민해서 풀어보세요."라고 써있어서 '무슨 두 시간까지나 걸린대ㅋㅋ;;'하고 코웃음 쳤는데... 정말... 또 다시 나는 한 톨의 먼지라는 것을 다시금 깨닫게 만든 문제. ㅠㅠ

 

처음 짠 코드(오답)

#include <stdio.h>
#include <stdlib.h>
 
 
int main(){
    int row, col;
    int i, j;
    int a, b;
    char **matrix;
 
    scanf("%d %d", &row, &col);
 
    matrix = malloc(sizeof(char *) * row);
 
    for (i = 0; i < row; i++)
        matrix[i] = malloc(sizeof(char) * (col + 1)); // 널 문자 포함
 
    for (i = 0; i < row; i++)
        scanf("%s", matrix[i]);
 
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                matrix[i][j] = '0';
            }
        }
    }
 
    for (i = 0; i < row; i++){
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                for (a = i-1; a <= i+1; a++){ // 오류가 발생한 부분
                    for (b = j-1; b <= j+1; b++){
                        if (matrix[a][b] == '*' && (a >= 0 && a < row && b >= 0 && b < col))
                            matrix[i][j] += 1;
                    }
                }
            }
        }
    }
 
 
    for (i = 0; i < row; i++){
        printf("%s\n", matrix[i]);
    }
 
    for (i = 0; i < row; i++)
        free(matrix[i]);
 
    free(matrix);
 
    return 0;
}

 

먼저 메모리 할당하는 것은 문제에서 널 문자 자리를 포함하라고 언급되어 있어서 실수하지 않고 무사히 끝낼 수 있었다. 코드를 다 작성하고 호기롭게 실행해봤는데, 행렬 크기와 문자열을 입력하는 것까지는 문제가 없었는데, 다 입력을 받고 나면 그냥 프로그램이 종료되어 버렸다. 

 

내가 사용하는 IDE에서는 에러 메세지는 뜨지 않길래 온라인 컴파일러에서 실행해보았고, 역시나 입력을 다 받은 후 프로그램이 종료되었고, 'segmentation fault'라는 메세지가 함께 출력되었다. 

 

이 메세지를 또 검색해보니 잘못된 메모리를 건든 경우에 발생하는 놈임을 알 수 있었다. 이에 코드를 작성할 때도 왠지 찜찜했던 

    for (i = 0; i < row; i++){
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                for (a = i-1; a <= i+1; a++){
                    for (b = j-1; b <= j+1; b++){
                        if (matrix[a][b] == '*' && (a >= 0 && a < row && b >= 0 && b < col))
                            matrix[i][j] += 1;
                    }
                }
            }
        }
    }
 
 

이 친구를 잠깐 빼고 실행해보았더니 문제없이 프로그램이 작동했다. 그렇다면 이 부분이 잘못되었다는 게 확실한데... 정확히 어떤 부분이 잘못되었는지 알기가 너무 힘들었다.

 

처음부터 a, b를 i-1, j-1로 두면 matrix[-1][-1]처럼 존재하지 않는 곳에 접근할 수 있다는 사실을 인지하고는 있었고, 이를 방지하기 위해 내 딴에는 if (matrix[a][b] == '*' && (a >= 0 && a < row && b >= 0 && b < col)) 라는 조건을 만들었다. 이 조건문 덕분에 실제 배열의 원소의 값만 건들기 때문에 문제가 없을 거라고 생각했다. 

 

그런데 오류는 사라질 생각을 안 하고 나도 마땅히 다르게 고칠 방법이 떠오르지 않고... 결국 코딩 도장 사이트에 있는 질문 게시판을 뒤적여봤다. 자주 묻는 질문에 "루프를 돌면서 인덱스를 벗어난 접근을 하게 되면, 주로 m[-1][-1]과 같은 접근을 하게 되면 메모리 오류가 발생합니다."라고 언급이 되어있었고 다른 분들이 질문한 내용도 이와 관련된 것들이 많았다. 그러다"i, j 루프 다음에 y, x 루프에 진입하기 전에 값을 검사해서 루프를 건너 뛰는 게 필요합니다. 보통은 continue를 사용합니다."라는 답변을 보았고, 아예 a, b를 활용한 for 루프를 본격적으로 활용하기 전에 a, b가 조건을 만족하는지를 검사해야 하나? 라는 생각이 들었다. 나도 continue를 활용하는 방향으로 코드를 수정해봤고...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
 
int main(){
    int row, col;
    int i, j;
    int a, b;
    char **matrix;
 
    scanf("%d %d", &row, &col);
 
    matrix = malloc(sizeof(char *) * row);
 
    for (i = 0; i < row; i++)
        matrix[i] = malloc(sizeof(char) * (col + 1));
 
    for (i = 0; i < row; i++)
        scanf("%s", matrix[i]);
 
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                matrix[i][j] = '0';
            }
        }
    }
 
    for (i = 0; i < row; i++){
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                for (a = i-1; a <= i+1; a++){
                    if (a == -1 || a == row)
                        continue;
                    for (b = j-1; b <= j+1; b++){
                        if (b == -1 || b == col)
                            continue;
                        if (matrix[a][b] == '*')
                            matrix[i][j] += 1;
                    }
                }
            }
        }
    }
 
 
    for (i = 0; i < row; i++){
        printf("%s\n", matrix[i]);
    }
 
    for (i = 0; i < row; i++)
        free(matrix[i]);
 
    free(matrix);
 
    return 0;
}
                    
 

결국 성공!!!!

 

처음에 continue 조건에서 row와 col을 row+1, col+1로 착각해서 또 성공적으로 실행되지 않았는데, 이것만 제대로 고쳐주니까 잘 작동했다. 야호!

 

그래서 나는 이미 인덱스를 벗어난 곳을 가지 않도록 조건까지 만들었는데 왜 문제가 발생하는 건지, continue를 활용하지 않고 나처럼 if문을 활용해서 작성하면 안 되는지 궁금했고, 이전에 짰던 내 코드를 디버거를 이용해서 하나씩 검사해보았다. 그러다 문득... 내 코드 속 조건 if (matrix[a][b] == '*' && (a >= 0 && a < row && b >= 0 && b < col)) 에 있는 matrix[a][b] == '*'가 이상함을 알아챘다. 확실히는 잘 모르겠지만 이 조건을 체크할 때 matrix[-1][0] 이런 식으로 인덱스를 벗어난 배열을 어쩔 수 없이 검사하게 되기 때문에 조건문이 거짓으로 판별되더라도 잘못된 메모리에 접근하게 되기 때문에 오류가 발생한 것 같다.

 

이렇게 보니 정말 간단한 걸 가지고 끙끙거렸던 것 같은데... 그래도 아직은 조금 많이 어려운 메모리, 포인터 개념을 다시 한 번 정리하는 데 큰 도움이 된 문제였다. 너무 짜증나서 그냥 포기하거나 답을 구글링해볼까 생각도 했는데 그래도 이렇게 내 힘으로 문제를 풀어서 정말 뿌듯하다! 이런 게 바로 코딩의 참맛일까. ꉂꉂ(ᵔᗜᵔ*) 

 

+ 답 설명과 비교

 

메모리를 할당하고 또 사용자의 입력을 받기 전에 memset 함수를 이용해서 메모리를 0으로 초기화해줘야 한다고 한다... memset 함수의 사용 또한 아직 익숙하지 않아서 잘 쓰지 않게 되는데 메모리 초기화하는 것도 많이 써봐야겠다.

 

또 해설에서는 "단, 주변을 탐색할 때 배열의 범위를 벗어나면(y < 0 || x < 0 || y >= m || x >= n) 요소에 접근하지 않고 건너뛰어야 합니다." 즉, 나처럼 for 루프 - a, for 루프 - b 각각에서 한 번 씩 검사하는 게 아니라 한번에 검사하는 것으로 설명하고 있다. 생각해보니 그게 더 깔끔하고 괜찮은 것 같다... 해설처럼 코드를 짠다면

    for (i = 0; i < row; i++){
        for (j = 0; j < col; j++){
            if (matrix[i][j] != '*'){
                for (a = i-1; a <= i+1; a++){
                    for (b = j-1; b <= j+1; b++){
                        if (a < 0 || b < 0 || a >= row || b >= col)
                            continue;
                        if (matrix[a][b] == '*')
                            matrix[i][j] += 1;
                    }
                }
            }
        }
    }

이렇게 되겠지? 

 

꽤나 힘들었던... 문제풀이 끝!