백준 - 1736 쓰레기 치우기

[Gold I] 쓰레기 치우기 - 1736

문제 링크

성능 요약

메모리: 2064 KB, 시간: 0 ms

분류

그리디 알고리즘

제출 일자

2024년 4월 3일 23:20:23

문제 설명

방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레기를 로봇을 사용해서 수거하려고 하는데, 로봇은 왼쪽 위에서 출발해 오른쪽 아래로 도착한다. 즉, 로봇은 현재 위치에서 오른쪽, 혹은 아래쪽으로밖에 이동할 수 없다.

이때, 모든 쓰레기를 수거하기 위해서 필요한 최소 로봇의 수를 출력하는 프로그램을 작성하시오.

입력

첫 행에는 N, M이 공백으로 구분되어 주어진다.

다음 N 행에 걸쳐 M 개의 수가 주어진다. 이 값이 0이면 해당하는 위치가 비어 있다는 뜻이고, 1이면 해당하는 위치에 쓰레기가 있음을 뜻한다.

출력

필요한 최소 로봇의 수를 출력한다.

풀이과정

처음 풀이는 쓰레기가 있는 위치를 모두 벡터에 넣고 쓰레기 갯수를 카운트 한 뒤에, 쓰레기 위치에서 bfs를 하는 것이었다. 오른쪽과 아래 두 방향만 확인하지만, 중복되는 위치를 계속 확인 하는 것 때문에 큐에 들어가는 좌표가 너무 많아져서 메모리 초과가 발생했다. 그렇다고 visit 배열을 만들어서 방문 처리를 하기에는 다른 경로로 가면서 같은 좌표를 여러 번 방문하는 것이 가능하기 때문에 방문 처리를 사용하는 것은 불가능하다.

결국 다른 사람의 풀이를 참고했다. 방법은 좌표를 순회하며 쓰레기를 만날 때마다 다시 그 위치로부터 재귀적으로 탐색을 시작하는 것이다. 좌표를 순회할 때의 제약 조건은 오른쪽과 아래 두 방향으로만 갈 수 있는 것이다. 이는 탐색할 때 offset을 걸어두는 것으로 해결할 수 있다. offset을 주면 현재 좌표에서 왼쪽이나 위는 확인할 수 없기 때문이다. offset보다 큰 좌표는 얼마든지 확인이 가능하다. 탐색 과정에서 만날 수 있는 쓰레기가 여러 개여도, 가장 가까운 쓰레기로부터 다시 재귀 탐색 후 바로 리턴하므로 한 번에 하나의 경로만 탐색할 수 있게 된다. 그러므로 최적해를 구할 수 있다.

쓰레기 세기

입력을 받을 때 쓰레기 갯수를 센다. 이는 반복문의 종료조건이 된다.

쓰레기가 있는 동안 반복문 실행

쓰레기가 0개가 아니라면 반복문을 실행한다.
반복문의 시작점에서 ans를 증가시킨다.

쓰레기 줍기

만약 현재 위치에 쓰레기가 있다면 배열에서 해당 위치의 값을 0으로 만들어주고, 쓰레기 갯수를 줄여준다. 이를 쓰레기를 줍는다고 표현하겠다.

종료 조건 확인

쓰레기 갯수를 줄일 때마다 쓰레기가 0개인지 확인한다. 0개라면 종료한다.

시작점 확인하기

시작점에 쓰레기가 있는 경우 쓰레기를 줍고 종료 조건을 확인하다.

탐색하기

아직 쓰레기가 남아있다면 탐색을 한다.
로봇은 항상 0,0에서 출발하기 때문에 탐색도 0,0부터 시작한다. 재귀적으로 탐색하기 위해서 0,0을 매개변수로 하여 함수를 호출한다.
시작 위치의 왼쪽이나 위로는 갈 수 없기 때문에 시작 좌표가 곧 offset이 된다. 2중 반복문으로 탐색하며 쓰레기를 찾는다.

쓰레기 발견 시 재귀 탐색

쓰레기를 발견하면 쓰레기를 줍고 종료조건을 확인한다.
아직 쓰레기가 남아있다면 해당 위치를 매개변수로 하여 다시 함수를 호출해 해당 위치를 시작점으로 하는 탐색을 다시 시작한다.
호출 이후, 바로 리턴하여 한 번에 여러 경로를 탐색할 수 없도록 한다.

코드

      

        
        
        
        
      
#include <iostream>
#define MX 105
using namespace std;
int N, M, map[MX][MX], cnt, ans;

void solve(int x, int y) {
    for (int i = x; i < N; i++) {
        for (int j = y; j < M; j++) {
            if (map[i][j]) {
                map[i][j] = 0;
                cnt--;
                if (!cnt) return;
                solve(i, j);
                return;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j]) cnt++;
        }
    }
    while (cnt) {
        ans++;
        if (map[0][0]) {
            map[0][0] = 0;
            cnt--;
            if (!cnt) break;
        }
        solve(0, 0);
    }
    cout << ans;
}