[백준 1012] 알고리즘 83일차 : 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

C++ 유기농 배추

연휴 전날 아침부터 배추에 지렁이 심음

 

2차원 배열에 배추 있는 위치가 1로 표시돼있고 상하좌우로 연결된 배추들끼리 인접해 있는 것이라고 할때

인접한 배추들의 그룹 수를 구하는 문제

바로 전날 푼 2667 문제에서 빌리지수만 구하는 문제 (집 개수 필요없음) 그래서 난이도 -1 인듯

 

접근방법

2667문제 거의 비슷하게 풀었다.

visit배열, map배열 써주고 다만 테스트케이스가 여러개라 반복문안에서 매번 배열들 초기화 해줘야한다.

2667에선 전역변수 한번 선언해주면 됐는데,, 쩝

상하좌우로 연결돼있는 것도 똑같아서 dfs함수 안의 코드도 집개수 세주는거만 빼면 똑같다.

그룹 개수(필요한 배추흰지렁이 개수)는 main에서 dfs함수가 끝날때마다 cnt++ 해주면 된다.

(풀이시간 : 약 18분)

 

오답노트

또 범위 초과한다고 런타임에러떠서 배열 사이즈 51로 늘려줬다. (같은 실수를 반복하는 어쩔 수 없는 휴먼)

나름 변명해보자면 50개라 인덱스 49까지인줄알고 이미 50이 안정권이라 생각함.. 아니었죠

 

*

사진설명

첫번째 제출 : 백준 런타임에러 이유 찾아주는거 처음 앎

런타임에러뜨면 에러 찾는중~ 이러면서 저렇게 OutOfBounds마냥 찾아줌 너무 좋다

두번째 제출 : C,C++ 표준스트림 끊어주고, cin untie 해줬을때 시간 0ms

세번째 제출 : C,C++ 표준스트림 안끊고, cin untie 안하고 제출해봄 시간 4ms

 

소스코드

#include <iostream>
using namespace std;
bool visit[51][51];
bool map[51][51];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

void dfs(int r, int c){
    visit[r][c] = true;
    for(int i = 0 ; i < 4 ; i++){
        int nr = r+dr[i];
        int nc = c+dc[i];
        if(map[nr][nc] && !visit[nr][nc]){
            dfs(nr,nc);
        }
    }
}

int main(){
    int t;
    cin >> t;
    for(int i = 0 ; i < t ; i++){
        int m,n,k;
        cin >> m >> n >> k;
        for(int q = 0 ; q < m ; q++){
            for(int w = 0 ; w < n ; w++){
                visit[q][w] = false;
                map[q][w] = false;
            }
        }
        int r,c;
        for(int j = 0 ; j < k ; j++){
            cin >> r >> c;
            map[r][c] = true;
        }
        int cnt = 0;
        for(int a = 0 ; a < m ; a++){
            for(int b = 0 ; b < n ; b++){
                if(!visit[a][b] && map[a][b]){
                    dfs(a,b);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}