글 읽기 - 문제 해결전략이 왜 그리디인지 모르겠습니다.

tddhot2 7년 전 1

- 힌트의 그리디 알고리즘이라 해서 그리디 알고리즘의 특징을 잘 생각해봤습니다.

- 선택의 순간에서 최적의 해를 선택한다가 그리디인데, 그렇게 생각하면은 3*3행렬로 가장 많이 변경할 수 있는 것이 최적의 해가 아닌가요? 많이 변경함으로써 전체적으로 변경해야할 수가 줄어든 거니깐요.

- 문제의 해답은 말그대로 최좌상측의 인덱스부터 하나씩 검사하면서 다를 경우 매번 3*3행렬로 뒤집는다인데.. 이게 왜 최적의 해가 되는건가요? 그냥 순서대로 뒤집어보다가 단순히 맞추는 것이 아닌가요? 그것이 어떻게 최저횟수가 되는 지 모르겠습니다.

- 아래의 소스코드는 제가 처음에 고안해낸 방식의 소스코드입니다. 물론 시간초과로 풀지는 못했습니다.

허접한 코더를 위해 설명해주시면 너무나도 감사하겠습니다.

#include <iostream>
using namespace std;

int A[50][50];
int B[50][50];
int x, y;
int ans(0);

bool compareAB() {
	for (int i = 0; i < x; i++)
		for (int j = 0; j < y; j++)
			if (A[i][j] != B[i][j])
				return false;
	return true;
}

int findMaximumChangePos() {
	pair<int, int> cPos(-1,-1);
	int max(0);

	for (int i = 0; i <= x - 3; i++) {
		for (int j = 0; j <= y - 3; j++) {

			//cout << i << "," << j << "부터 3x3행렬 검사" << endl;

			int temp(0);
			//해당 좌표 i,j부터 3x3크기만큼 변경했을 때 정답인 값 개수
			for (int subX = i; subX < i + 3; subX++)
				for (int subY = j; subY < j + 3; subY++)
					if (!A[subX][subY] == B[subX][subY])
						temp++;

			//cout << "총 교체 가능 개수 = " << temp << endl;
			if (temp > max) {
				max = temp;
				cPos.first = i;
				cPos.second = j;
			}
		}
	}
	if (cPos.first != -1) {
		for (int i = cPos.first; i < cPos.first + 3; i++)
			for (int j = cPos.second; j < cPos.second + 3; j++)
				(A[i][j] == 1) ? A[i][j] = 0 : A[i][j] = 1;
		return 1;
	}
	else
		return 0;
	
}


int main() {
	
	cin >> x >> y;


	// 행렬 A,B 입력 시작
	for (int i = 0; i < x; i++) {
		char str[50];
		cin >> str;
		int j = 0;
		while (str[j] != 0) {
			A[i][j] = str[j] - '0';
			j++;
		}
	}
	for (int i = 0; i < x; i++) {
		char str[50];
		cin >> str;
		int j = 0;
		while (str[j] != 0) {
			B[i][j] = str[j] - '0';
			j++;
		}
	}
	// 행렬 입력 종료



	// 비교 및 스왑 연산 시작
	int flag = 0;
	while (!compareAB()) {
		
		if (findMaximumChangePos() == 1)
			ans++;
		else
			flag = 1;

	}
	// 종료



	if (flag == 1)
		cout << -1;
	else
		cout << ans;

	return 0;
}

alexroh 3년 전 24

3년 전 질문이라서 답변은 의미가 없다고 생각하지만 다른 분들을 위해, 그리고 제 공부를 위해 써보겠습니다.

Q1. 3 * 3행렬로 가장 많이 변경할 수 있는 것이 최적의 해가 아닌가요? 많이 변경함으로써 전체적으로 변경해야할 수가 줄어든 거니깐요.

→ 뒤집는 연산의 특성상 많이 변경하는 것은 의미가 없습니다. 따라서 최적의 해에 가까워진다고 볼 수 없습니다.

Q2. 이게 왜 최적의 해가 되는 건가요? 그냥 순서대로 뒤집어 보다가 단순히 맞추는 것이 아닌가요? 그것이 어떻게 최저횟수가 되는지 모르겠습니다.

→ 이 문제의 목적은 행렬 A를 행렬 B로 바꾸는 것입니다. 따라서 행렬 A에서 0인데 B에서 1인 칸이 있으면 반드시 뒤집어야 합니다.

문제는 그 연산을 몇 번 하느냐입니다. 뒤집는 연산의 특성상 2번 이상 뒤집는 것은 의미가 없습니다. 2번 뒤집으면 원래대로 돌아오고, 3번 뒤집는 것은 1번 뒤집는 것과 같습니다.

이때 최적의 선택은 "반드시 뒤집어야 하는 칸을 뒤집되, 뒤집는 횟수를 최소화하는 것" 입니다. 즉, 이미 뒤집은 칸을 2번이나 3번 뒤집지 않습니다.

이 전략은 다음과 같이 구현됩니다. 행렬을 순서대로 탐색하면서, "반드시 뒤집어야 하는 부분이 있으면" 바꿉니다. 뒤집을 필요가 없으면 확정하고 넘어갑니다.

그러다 어떤 칸을 만났는데 그 칸을 뒤집으면 이전에 확정시켜 놓은 칸이 다시 뒤집힐 경우, 살펴보지 않고 넘어갑니다.

이렇게 하면 5 × 5 행렬의 경우, 좌상단부터 3 × 3 부분에 있는 칸만 확정해도 이 행렬을 B로 변환 가능한지 아닌지를 알 수 있습니다.

이 알고리즘은 매 순간 ‘뒤집어야 하는 칸의 뒤집는 횟수를 최소화한다’는 점에서 그리디 알고리즘으로 분류된다고 생각합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 해결전략이 왜 그리디인지 모르겠습니다.

tddhot2 7년 전 1

alexroh 3년 전 24

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말