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

1736번: 쓰레기 치우기

 이 문제는 10월 9일에 있었던 ICPC Seoul Regional 2021 예선 K번(Treasure Hunter)이랑 매우 유사하다. N과 M의 크기 때문에 1736번 문제가 훨씬 더 쉽다. 대회 때 시간이 없어서 K번은 해결하지 못하였는데, 한 선배가 백준에 똑같은 문제가 있다고 보여주셔서 풀게 되었다.

 

---

풀이

코드의 구조를 간단하게 나타내면 다음과 같다.
1. 입력을 받으면서 쓰레기의 개수(trash)를 계산해준다.
2. 쓰레기의 개수(trash)가 0이 될 때 까지 청소기 1개를 사용하는 것(clean 함수)을 반복한다.
3. 즉, while문을 돈 횟수(=청소기 사용 개수)가 정답(ans)이 된다.

재귀를 이용해 구현한 clean함수를 살펴보자.
input은 현재 청소기의 위치(행, 열)이다.
1. 현재 청소기의 위치를 기준으로 (오른쪽-> 아래쪽) 순서로 탐색을 진행한다.
2. 쓰레기를 발견하면 쓰레기를 치우고, 치운 위치로 이동한다.
3. n-1행 m-1열에 도착하면 함수를 종료한다.


문제에 나온 예제 입력 1과 같이 입력을 받게 된다면 아래와 같이 탐색한다.

빨강 - 연두 - 파랑 순서

첫 번째 while문에서의 clean함수의 경로는 빨강,
두 번째 whlie문에서의 clean함수의 경로는 연두,
세 번째 while문에서의 clean함수의 경로는 파랑이다.

while문을 3번 돌고 나면 남은 쓰레기가 없으므로 while문을 빠져나와 답인 3(while문을 돈 횟수)을 출력하게 된다.

---

코드

#include <bits/stdc++.h>
#define endl '\n'
#define INF 9876543210
using namespace std;
using ll = long long;

ll n, m, trash = 0, ans = 0;
ll room[100][100];

void clean(ll x, ll y) {
    if (x == n - 1 && y == m - 1) {
        if (room[x][y] == 1) {
            trash--;
            room[x][y] = 0;        
        }
        return;
    }
    for (ll i = x; i < n; i++) {
        for (ll j = y; j < m; j++) {
            if (room[i][j] == 1) {
                room[i][j] = 0;
                trash--;
                clean(i, j);              
                return;
            }
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) { 
            cin >> room[i][j];
            if (room[i][j] == 1) trash++;
        }
    }
    while (trash > 0) {
        ans++;
        if (room[0][0] == 1) {
            room[0][0] = 0;
            trash--;
        }
        clean(0, 0);
    }
    cout << ans << endl;

    return 0;
}