[백준(BOJ) / C][Silver Ⅴ] 1343번 : 폴리오미노

문제

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노

---

풀이

해당 문제는 '재귀함수'를 사용하여 풀었습니다.

board[idx]가 ' . ' 이라면 해당 idx를 넘어가며 1를 더해줍니다.

 

만약 아니라면 'X'라는 뜻이므로 'X'가 아닌 배열까지 length값을 올려줍니다.

이렇게 하는 이뉴는 해당 'X' 문자열의 길이를 알수있기 때문입니다.

 

이렇게 알게된 'X'의 길이가 홀수라면 채워넣을수있는 방법은 없다는 뜻이기에 '-1'을 출력하며 컴파일을 종료시키고

아니라면 PrintPoli 함수를 호출하여 해당 result 배열에 집어 넣습니다.

 

여기서 값을 집어넣으면 그 넣은 만큼 길이도 줄어들게 되는데 그것의 값을 다시 PrintPoli 함수에 전달하여 그 값만큼 값을 집어넣게 됩니다.

 

그리고 넣은 만큼 idx도 늘어나기 때문에 그 값만큼 idx에 더해주면 idx는 집어넣은 문자열 앞을 가르키게 됩니다.

 

값을 넣다보면 idx가 board의 길이보다 길어지면 해당 문자열을 다 보았다는 뜻이기 때문에 반복문을 탈출하고

그동안 result에 넣은 값들을 출력합니다.

 

간단하게 말하자면, 'X' 문자열들을 한 덩어리로 보고 ' . ' 은 그것을 나누는 기준으로 생각하여 뭉텅이들을 어떻게 바꾸는가에 대해 고민을 하시면 쉽게 풀수있다 생각합니다.

---

소스코드

#include <stdio.h>
#include <string.h>

// result 배열에 'X' 의 개수에 따라 'A' 또는 'B'를 채워 넣는다.
void PrintPoli(int _length, char _result[], int _idx);

int main(void)
{
	int length, idx = 0, boardLength;
	char board[51], result[51];
	
	scanf("%s", board);
	boardLength = strlen(board);
		
	while(1)
	{	
		if(board[idx] == '.')
		{
			result[idx] = '.';
			idx++;
			continue;
		}
		
		// length를 0으로 초기화 한다.
		// 만약 이전에 length로 'X' 의 개수를 세었다면 다시 새로
		// 'X'의 개수를 세야하기 때문에.
		length = 0;
		
		// 현재 idx를 기준으로 'X'가 아닐때까지 while문을 돌리면
		// 해당 'X'의 개수를 구합니다.
		while(board[idx + length] == 'X')
		{
			length++;
		}
		
		// 만약 length가 홀수라면 채워넣을 방법이 없기 때문에
		// '-1'을 출력하고 종료합니다.
		if(length % 2 != 0)
		{
			printf("-1");
			return 0;
		}
		// 그것이 아니라면 채워넣습니다.
		else
		{
			// PrintPoli 함수에 'X'의 길이, 결과값을 넣을 배열, 현재 idx를 전달합니다.
			PrintPoli(length, result, idx);
			
			// 채워넣는것이 끝난다면 그 길이 만큼 idx에 넣어
			// 채워넣은 곳들을 뛰어 넘습니다.
			idx += length;
		}	
		
		// idx가 보드 크기보다 크다면 다 채워넣었다는 뜻이기 때문에 
		// 반복문을 빠져나옵니다.
		if(idx  >= boardLength)
		{
			break;
		}
		
	}
	
	// 결과값을 출력합니다.
	for(int i = 0; i < boardLength; i++)
	{
		printf("%c", result[i]);
	}
	
	return 0;
}

// result 배열에 'X' 의 개수에 따라 'A' 또는 'B'를 채워 넣는다.
void PrintPoli(int _length, char _result[], int _idx)
{
	// 다 채워진다면 _length는 0이기 때문에 자동적으로 함수를 나온다.
	// 만약 _length(길이)가 4 이상이라면
	if(_length >= 4)
	{
		// 'AAAA'를 result에 넣는다.
		for(int i = 0; i < 4; i++)
		{
			_result[_idx + i] = 'A';
		}
		
		// 'X'의 길이를 4만큼 뺀다.
		_length -= 4;
		// 넣은 만큼 idx를 더해준다.
		_idx += 4;
		
		// 다시 PrintPoli를 호출
		PrintPoli(_length, _result, _idx);
	}
	// 만약 _length(길이)가 2 라면
	else if(_length == 2)
	{
		// 'BB'를 result에 넣는다.
		for(int i = 0; i < 2; i++)
		{
			_result[_idx + i] = 'B';
		}
		
		// 'X'의 길이를 2만큼 뺸다.
		_length -= 2;
		// 넣은 만큼 idx를 더해준다.
		_idx += 2;
		
		// 다시 PrintPoli를 호출
		PrintPoli(_length, _result, _idx);
	}
		
}