백준 1018번 : 체스판 다시 칠하기

문제 접근 & 오류

---

처음에는 이어지는 문자가 앞이랑 같으면 체스판이 안 되니 고치는 방식으로 구현했다. 이때 board 에 직접 고쳐넣었는데 첫번째 예제 case 인 한 문자만 고치면 되는 경우에서는 잘 됐는데, 판단의 근거가 될 board 가 고쳐지니 두번째 예제 case 에서는 완전히 꼬였다. 그래서 2차원 배열을 하나 더 만들어서 체스판 하나 확인할 때마다 복사하는 것도 생각했는데 최악의 경우 43*43번 복사해야 돼서 메모리 낭비가 말도 안돼보였다. 이때 문득 bool type, 이전 요소가 잘못되어 (바뀌지는 않았지만) 바뀌었다고 판단할건지 정하는 isChange 를 만들면 효과적일 것 같아서 구현해봤는데 예상 그대로 잘 되었다.

 

예제 case 에서 잘 돌아가서 그대로 제출했는데 '틀렸습니다'가 나왔다. 예전같으면 '맞왜틀.., 맞왜틀..'거리면서 머리 식힌다는 핑계로 쉬었을텐데 철이 든건가 '반례 만들어보자!' 라는 생각이 들었다 ㅋㅋㅋ. isChange 가 연속적으로 바뀌는 부분에서 이상이 생겼을 수 있다고 생각해서 다음과 같은 반례를 만들어봤다.

 

반례 실행 결과

답은 32 이어야 되는데 출력 결과는 31이다. 알고보니 28행 if 문에서 isChange = !(isChange); 를 isChange=false 로 바꾼다는 걸 깜빡했다. 처음에 저렇게 구현한 이유는 한 번 바꾼다고 판단할때마다 반전시켜서 논리 구조를 만족시키겠다는 생각이었는데 오히려 연속적으로 틀릴 경우 논리적 오류가 생겨서 그냥 Change 하면 false 가, 정상이면 true 가 할당되게 했다. (변수 이름은 isChange 인데 바뀌면 false 다 ㅋㅋ)

 

제대로 넣어주니 '맞았습니다'를 받았당. Yummy~

 

 

문제 풀이 -  틀렸습니다

---

#include <iostream>

using namespace std;

char board[50][50];

int check_diff(int x,int y)
{
	int cnt = 0;
	bool isChange=true;
	
	for(int i=x; i<x+8; ++i)
	{
		for(int j=y; j<y+7; ++j)
		{
			if(!(isChange ^ board[i][j]==board[i][j+1]))
			{
				isChange = false;
				cnt++;
				
				//cout<<"[L]cnt++ when ("<<i<<","<<j+1<<")\n";
			}
			
			else
				isChange = true;
			
		}
		if(i<x+7 && !(isChange ^ board[i][y+7]!=board[i+1][y]))
		{
			isChange = !(isChange);
			cnt++;
			
			//cout<<"[N]cnt++ when ("<<i+1<<","<<y<<")\n";
		}
	}
	
	if(cnt>32)
		cnt=64-cnt;
	
	return cnt;
}

int main(void)
{
	int N,M,min=64,tmp;
	cin>>N>>M;
	
	for(int i=0; i<N; ++i)
		for(int j=0; j<M; ++j)
			cin>>board[i][j];
	
	for(int i=0; i<N-7; ++i)
		for(int j=0; j<M-7; ++j)
		{
			tmp=check_diff(i,j);
			//cout<<"("<<i<<","<<j<<") -> "<<tmp<<'\n';
			if(min>tmp)
				min=tmp;
		}
	
	cout<<min<<'\n';
	
	return 0;
}

예제 case 실행 결과

 

문제 풀이 - 맞았습니다.

---

#include <iostream>

using namespace std;

char board[50][50];

int check_diff(int x,int y)
{
	int cnt = 0;
	bool isChange=true;
	
	for(int i=x; i<x+8; ++i)
	{
		for(int j=y; j<y+7; ++j)
		{
			if(!(isChange ^ board[i][j]==board[i][j+1]))
			{
				isChange = false;
				cnt++;
				
				//cout<<"[L]cnt++ when ("<<i<<","<<j+1<<")\n";
			}
			
			else
				isChange = true;
			
		}
		if(i<x+7 && !(isChange ^ board[i][y+7]!=board[i+1][y]))
		{
			isChange = false;
			cnt++;
			
			//cout<<"[N]cnt++ when ("<<i+1<<","<<y<<")\n";
		}
		else
			isChange = true;
	}
	
	if(cnt>32)
		cnt=64-cnt;
	
	return cnt;
}

int main(void)
{
	int N,M,min=64,tmp;
	cin>>N>>M;
	
	for(int i=0; i<N; ++i)
		for(int j=0; j<M; ++j)
			cin>>board[i][j];
	
	for(int i=0; i<N-7; ++i)
		for(int j=0; j<M-7; ++j)
		{
			tmp=check_diff(i,j);
			//cout<<"("<<i<<","<<j<<") -> "<<tmp<<'\n';
			if(min>tmp)
				min=tmp;
		}
	
	cout<<min<<'\n';
	
	return 0;
}

예제 case + 반례 case

 

결과

---