[백준] 1012 유기농 배추 c++/무수한 틀림과 함께

- 언제 풀었는지, 어떻게 풀었는지 기억도 안 나는 문제들 다시 푸는 중

 

 

---

• 런타임 에러 - 제출 코드

#include <iostream>

using namespace std;

int M,N;
int **arr;
int res = 0;

void check(int r, int c)
{
    arr[r][c] = 0;

    if(arr[r][c+1] == 1 && c+1 <= N)
        check(r, c+1);

    if(arr[r+1][c] == 1 && r+1 <= M)
        check(r+1, c);
}

int main()
{
    int T;
    cin >> T;
    for (int i=0; i<T; i++)
    {
        int K;
        cin >> M >> N >> K;
        res = 0;

        arr = new int*[M];
        for(int j=0; j<M; j++)
            arr[j] = new int[N];

        for(int n=0; n<K; n++)
        {
            int r, c;
            cin >> r >> c;
            arr[r][c] = 1;
        }

        for(int k=0; k<M; k++)
            for(int l=0; l<N; l++)
            {
                if(arr[k][l] == 1)
                {
                    res++;
                    check(k, l);
                }
            }
                
        cout << res;
    }
}

처음 아이디어: 배열 인덱스가 어차피 0,0 부터 오른쪽, 아래로 전부 도니까 해당 칸이 1이면 오른쪽, 아래칸만 봐줘도 된다고 생각했음 (<- 틀림)

 

=> 런타임 에러 이유: check 함수에서 c+1과 r+1이 범위 벗어났을 때 확인을 안해줬음

---

• 틀렸습니다 - 수정 사항
  • 계속 12%에서 틀렸다고 떴음 
  • 일단 런타임 에러 이유 고쳐주고
  • cout << res 부분에서 개행문자 붙여주고
  • 배열 동적할당 해제 해주고 (해제 안하고 제출 해봤는데 맞았다고 뜨긴 함, 틀린 이유는 아닌듯)
  • 그리고 제일 중요한 것 
    • 질문 게시판의 답변에서 반례를 찾았음
    • 아래 그림의 경우 답이 1이 나와야 되는데 왼쪽 체크를 안해버려서 답이 2가 되는 거임
    • 그래서 왼쪽, 위쪽 체크하는 로직도 추가함

---

• 최종 제출 코드

#include <iostream>

using namespace std;

int M,N;
int **arr;
int res = 0;

void check(int r, int c)
{
    arr[r][c] = 0;

    if(c-1 >= 0)
        if(arr[r][c-1] == 1)
            check(r, c-1);

    if(c+1 <= N-1)
        if(arr[r][c+1] == 1)
            check(r, c+1);

    if(r-1 >= 0)
        if(arr[r-1][c] == 1)
            check(r-1, c);

    if(r+1 <= M-1)
        if(arr[r+1][c] == 1)
            check(r+1, c);
}

int main()
{
    int T;
    cin >> T;
    for (int i=0; i<T; i++)
    {
        int K;
        cin >> M >> N >> K;
        res = 0;

        arr = new int*[M];
        for(int j=0; j<M; j++)
        {
            arr[j] = new int[N];
            for(int t=0; t<N; t++)
                arr[j][t] = 0;
        }
            

        for(int n=0; n<K; n++)
        {
            int r, c;
            cin >> r >> c;
            arr[r][c] = 1;
        }

        for(int k=0; k<M; k++)
            for(int l=0; l<N; l++)
            {
                if(arr[k][l] == 1)
                {
                    res++;
                    check(k, l);
                }
            }
                
        cout << res << "\n";
    }

    for(int i=0; i<M; i++)
        delete[] arr[i];

    delete[] arr;
}

---