[백준] 1736번 쓰레기 치우기 (C++)

https://www.acmicpc.net/problem/1736

 

 

이 문제는 N X M 격자가 주어지고 격자에는 0과 1의 요소만 주어지며 1은 쓰레기를 나타내고 0은 빈 곳을 나타낸다.

이때 모든 칸에 로봇 청소기를 놓을 수 있으며 로봇 청소기는 해당 칸을 기준으로 오른쪽과 아래로만 이동할 수 있다.

 

이때 모든 칸의 쓰레기가 없게 하는 최소 로봇 개수를 구하는 문제이다.

 

처음엔 재귀를 사용하여 완전탐색하는 경우를 생각하였다. 하지만 문제 접근을 잘못하였고 쓰레기를 발견했을때 오른쪽과 아래쪽을 재귀호출하여 잘못된 로직으로 작성하였다.

 

하지만 실제로는 현재 칸에서 오른쪽 또는 아래 칸으로 갈 수 있기 때문에 갈 수 있는 칸만 탐색을 하여 쓰레기를 만날때마다 재귀호출을 하고 바로 끝나면 리턴하여 종료할 수 있게 작성하였다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 0};
int dy[] = {0, 1};
int N, M, trash, answer;
int graph[101][101];

void func(int x, int y) {
    for(int i = x; i < N; i++) {		// x,y를 고정했기 때문에 현재 칸 기준으로 아래 오른쪽 탐색
        for(int j = y; j < M; j++) {
            if(graph[i][j]) {
                trash--;			// 쓰레기 개수 차감
                graph[i][j] = 0;	// 현재 칸을 빈칸으로 채움
                func(i, j);
                return;		
            }
        }
    }
}

void solve() {
    while(trash > 0) {
        func(0, 0);
        answer++;
    }

    cout << answer;
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];

            if(graph[i][j] == 1) {
                trash++;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}