[백준/BOJ] 1736. 쓰레기 치우기 [Gold 2]

1736. 쓰레기 치우기

문제출처 : https://www.acmicpc.net/problem/1736

참고블로그 : https://dong-gas.tistory.com/22

code

#include <iostream>
using namespace std;

long long garbage[100][100];
int cnt[100], end[100];
int N, M, result = 0, trash = 0;

void clean(int x, int y)
{
	if (x == N - 1 && y == M - 1)
	{
		if (garbage[y][x] == 1)
		{
			garbage[y][x] = 0;
			trash--;
		}
		return;
	}

	for (int i = y; i < N; i++)
	{
		for (int j = x; j < M; j++)
		{
			if (garbage[i][j] == 1)
			{
				garbage[i][j] = 0;
				trash--;
				clean(j, i);
				return;
			}
		}
	}
	return;
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> garbage[i][j];
			if (garbage[i][j] == 1)
				trash++;
		}

	while (trash > 0)
	{
		result++;
		if (garbage[0][0] == 1)
		{
			garbage[0][0] = 0;
			trash--;
		}
		clean(0, 0);
	}

	cout << result;
	return 0;
}

처음에 재귀함수를 안쓰고 그냥 가로줄에 1이 없을때까지 돌고 세로줄에 1이 있으면 다시 그줄 가로줄을 검색하고 반복하는식으로 코드를 짰는데 안풀려서 끙끙앓고 있었는데, 블로그를 보고나서 재귀함수를 이용하면 쉽게 풀린다는것을 알았다. 다른일을 하면서 문제풀라고하니까 집중도 별로 안되고 제대로 못짠것 같아 아쉽다.. 다음부터는 진짜 집중해서 풀어야겠다 ㅠㅠ

2023.07.21 수정

#include <iostream>
using namespace std;

long long garbage[100][100];
int cnt[100], end[100];
int N, M, result = 0, trash = 0;

void clean(int x, int y)
{
	if (x == N - 1 && y == M - 1)
	{
		if (garbage[x][y] == 1)
		{
			garbage[x][y] = 0;
			trash--;
		}
		return;
	}

	for (int i = y; i < N; i++)
	{
		for (int j = x; j < M; j++)
		{
			if (garbage[i][j] == 1)
			{
				garbage[i][j] = 0;
				trash--;
				clean(j, i);
				return;
			}
		}
	}
	return;
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> garbage[i][j];
			if (garbage[i][j] == 1)
				trash++;
		}

	while (trash > 0)
	{
		result++;
		if (garbage[0][0] == 1)
		{
			garbage[0][0] = 0;
			trash--;
		}
		clean(0, 0);
	}

	cout << result;
	return 0;
}

garbage[y][x]에서 왜 x,y위치가 바꼈냐고 댓글을 달아주셔서 다시봤는데 garbage[x][y]로 해도 성공이였다. 그냥 내 실수였던것같다.