[C/코딩도장] 38.8 지뢰찾기 심사문제

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
    int m,n;
    
    scanf("%d %d", &m , &n);

    //지뢰판, 정답판 생성
    char matrix[m][n+1];
    int count[m+2][n+2];

    //지뢰판 입력받기
    for (int i = 0; i < m; i++)
    {
      scanf("%s", matrix[i]);   
    } 

    //정답판 초기화
    for(int i=0;i<m+2;i++)
    {
      for(int j=0;j<n+2;j++)
          count[i][j]=0;
    }


    //정답판 채우기
    for (int i = 0; i < m; i++)
    {
      for(int j=0;j<n;j++)
      {
        if(matrix[i][j]=='*')
        {
          count[i+1][j+1]=74;
          
          /*
          count[i][j]++;
          count[i+1][j]++;
          count[i+2][j]++;
          count[i][j+1]++;
          count[i+1][j+1]++;
          count[i+2][j+1]++;
          count[i][j+2]++;
          count[i+1][j+2]++;
          count[i+2][j+2]++;
		  */
          
          // 이 반복문으로 하면 오류남 -> 오류해결!
          for(int a=i;a<=i+2;a++){
            for(int b=j;b<=j+2;b++)
              count[a][b]++;
          }
          
        }   
      }
    }  


  
    //정답판 출력
    for(int i=1;i<m+1;i++)
    {
      for(int j=1;j<n+1;j++)
        {
          if(count[i][j]<10){
            printf("%d",count[i][j]);
          }
          else{
            printf("*");
          }
        }
      printf("\n");
    }
  
    return 0;
}

 

 

<문제 해결 로직에 대한 2가지 관점>

1. 지뢰 아닌 것 (.) 을 기준으로 한다.

인간인 나의 일반적인 계산법이다. 모든 배열 원소를 방문하면서 주변 8개의 원소를 확인하고 지뢰의 개수를 새는 것이다. 하지만 이 방법은 m*n*8번이나 걸린다. 너무 오래 걸리는 것 같다.

 

2. 지뢰(*) 를 기준으로 한다.(채택)

주어진 예시에서 지뢰의 개수가 더 적으니까 지뢰를 기준으로 하면, 모든 배열 원소를 방문할 필요 없이 지뢰를 찾아서 지뢰 주변의 8개의 배열원소의 카운트를 하나씩 올려준다. 그러면 지뢰의 개수를 x라고 하면 x*8만 하면 된다.

 

 

 

<구현 시 고려사항>

1. 배열의 양 끝, 즉, i=0, i=m-1, j=0, j=n-1 에 있는 원소들은 주변에 8개의 원소가 있는게 아니라 양 끝단에 있어서 좌,우, 위, 아래 중에 존재 하지 않는 원소가 생긴다. 그래서 이것을 일일이 0보다 작거나 m-1, n-1 보다 크거나 막 이렇게 나누려고 했다가 머리 터질 뻔해서.. 그냥 정답판을 따로 만들고 m+2, n+2 크기로 아예 키워버렸다. 그러고 출력할 때는 필요한 m*n 부분만 출력해버렸다. 이것은 야매인가..?

 

2. 일단 그냥 배열로 했는데, 모범답안은 이중포인터를 사용해서 메모리 할당하고 해제하고 막 그렇게 했다. 아직도 나는 포인터, 메모리할당이 낯설고 어렵나보다. 그런데 내가 푼대로 배열로 저렇게 해도 되는건가? 답은 맞았는데..

 

 

 

<질문사항>

1. 배열과 포인터, 두 개를 모두 사용할 수 있는지, 어느 것이 더 효율적인지? 장단점은?

2. 중간에 주석처리한 for문을 돌리면 왜 오류가 나는가? 일일이 하나씩 count 올려주면 오류 안 나는데.. for문이 문법적으로 잘못된 것은 없는 것 같은데..?

 

 

 

코린이입니다. 제 질문에 답해주실 선배님들, 전문가님들, 아무나 찾습니다~

 

 

---

 

<피드백 2 from 쏠>

1. 문제상황 : m, n을 입력받아 배열의 크기를 동적으로 정해야 하는 경우

• 배열 : 배열의 크기를 동적으로 정할 수 없다(정적할당). 배열 선언 시 반드시 크기도 함께 정해줘야 한다. 단, 어떤 컴파일러는 가능하다고 한다. (참고 : 가변길이배열 -> 나도 모르는 사이에 가변길이배열을 사용한 듯 싶다. 문제의 경우에는 배열의 크기가 매우 작아서 가능했던 것 같다. )
• 포인터 : 포인터를 배열처럼 사용하기. 배열의 크기를 입력받아 메모리 동적 할당을 하자. 안전하고 메모리 낭비가 적다. 반드시 메모리 해제를 해줘야한다.

 

 

<피드백 2 from 나자신>

2. 문제의 for문에서 바깥 말고 안쪽 for문에 b++을 j++로 잘못 썼었다. -> 해결!

 

 

 

---

보너스로 모범답안이었던 이중포인터로 동적할당을 사용한 코드를 작성해보았다.

 

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>  //memset함수가 선언된 헤더파일

int main(void)
{
    int m,n;
    
    scanf("%d %d", &m , &n);

    //지뢰판 생성
    char** matrix = malloc(sizeof(char*)*m);
    for(int i=0;i<m;i++)
    {
      matrix[i]=malloc(sizeof(char)*(n+1));    
    }

    //정답판 생성
    int** count=malloc(sizeof(int*)*(m+2));
    for(int i=0;i<m+2;i++)
    {
      count[i]=malloc(sizeof(int)*(n+2));    
    }
  
    //지뢰판 입력받기
    for (int i = 0; i < m; i++)
    {
      scanf("%s", matrix[i]);   
    } 

    //정답판 초기화
    for(int i=0;i<m+2;i++)
    {
      memset(count[i],0,sizeof(int)*(n+2));
    }

  
    //정답판 채우기
    for (int i = 0; i < m; i++)
    {
      for(int j=0;j<n;j++)
      {
        if(matrix[i][j]=='*')
        {
          count[i+1][j+1]=101;  //지뢰를 100 이상의 숫자로 구분하여 인식
        
          for(int a=i;a<=i+2;a++){
            for(int b=j;b<=j+2;b++)
              count[a][b]++;
          }
        }   
      }
    }  

  
    //정답판 출력
    for(int i=1;i<m+1;i++)
    {
      for(int j=1;j<n+1;j++)
      {
        if(count[i][j]>100)
        {
          printf("*");
        }
        else if(count[i][j]<10)
          printf("%d",count[i][j]);
      }
      printf("\n");
    }


    //동적 메모리 해제
    for(int i=0;i<m;i++)
    {
      free(matrix[i]); 
    }

    free(matrix);

    for(int i=0;i<m+2;i++)
    {
      free(count[i]);    
    }

    free(count);
  
    return 0;
}

 

 

 

 

---

<참고사이트>

• 포인터와 배열, 동적할당
  https://blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nsj6646&logNo=221495948312
• 가변길이배열(Variable-length Array)
  https://jungpaeng.tistory.com/89
• 이중포인터를 2차원 배열처럼 사용하기
  https://dojang.io/mod/page/view.php?id=319

• 메모리 초기화 : memset함수 사용하기
  https://dojang.io/mod/page/view.php?id=287