백준) 16924번: 십자가 찾기 in C

Problem

16924번: 십자가 찾기

 

Solution.

 

먼저 in_arr에 '*'인 경우 1, 나머지는 0으로 2차원 배열을 만든다.

 

그리고 행, 열의 각 index를 1에서부터 N-2, M-2 까지 탐색하며 (for문의 i, j 이용)

in_arr[i][j] 가 1인 경우,(즉 십자가의 중심일 가능성이 있다. 아니면 그냥 별이덩가)

 k를 1로 초기화 시키고(k는 십자가의 크기를 의미) 난 뒤에 1씩 증가시키면서 k 범위 내의 십자가가 만들어지는지 확인했다. (행의 i-k, i+k, 그리고 열의 j-k, j+k index에 있는 in_arr의 값이 모두 1이면 십자가 모양이라는 뜻이다.)

 

예를 들어

. * .

* * *

. * .

일때,

index가 각각 1, 1인 경우 k가 1인, 즉 십자가의 크기가 1이고 그 중심이 index 1, 1 인 십자가임을 알 수 있다.

in_arr[0][1], in_arr[2][1], in_arr[1][0], in_arr[1][2] 값이 모두 1이니까.

 

그리고 out_arr과 pic_arr 배열은 각각

out_arr : 만들어지는 십자가의 크기를 십자가 가운데 행, 열 index에 저장한 배열.

pic_arr : out_arr을 바탕으로 만들어지는 실제 그림의 배열.

을 의미한다.

 

이때 답을 print 할라면 out_arr만 있으면 되지 왜 굳이 pic_arr를 또 만들었는지 생각할 수도 있다.

pic_arr은 사실 내가 문제를 잘못 이해해서 그 부분을 보완하기 위해 새로 만든 배열이다.

out_arr만 가지고 답을 print하면 예제 입력 1번과 2번은 잘 나온다. 즉 십자가로 input 배열의 그림을 만들 수 있을 때는 원하는 형식에 맞게 결과가 잘 나오는 것이다.

하지만 내가 짠 알고리즘대로라면 십자가로 그림을 만들 수 없을 때(예제 입력 3번과 4번)에도 -1이 나오지않고 다른 답변이 나온다.

 

예제 3번을 보면

.*...
***..
.*...
.*...
.....

에서 our_arr만 보면 출력 답안은 원래 답변인 -1이 안나오고

1

2 2 1

이 나온다.

즉 내가 out_arr를 통해 알아낸 것은 input 배열 그림을 십자가만으로 만들 수 있는 것인지가 아니라,

input 배열 그림 안에 어떤 십자가가 있는지였다.

이는 다르게 생각해보면 out_arr를 통해 만들어진 그림과 input 배열을 통해 받아온 그림이 다르다면 십자가만 가지고는 input 배열의 그림을 만들 수 없다는 게 된다. (out_arr는 십자가 모양만 가지고 만든 배열이므로)

따라서 pic_arr을 만들어서 out_arr 내용으로 만들어진 배열 그림과 input 배열 그림을 비교하는 내용을 추가했다.

 

진짜 단순무식하게 푼 방법이라서 시간 복잡도가 높아서인지 채점할 때도 시간이 좀 오래걸리더라. (그래도 런타임 에러는 안 떠서 다행)

분명히 이것보다 나은 풀이법이 인터넷에는 널렸을 것이다.

 

Code.

#include <stdio.h>

int main(){
	int N, M, i, j, k, l, count = 0;
	char in_arr[100][100] = {0, };
	int out_arr[100][100] = {0, };
	char pic_arr[100][100] = {0, };
	
	scanf("%d %d", &N, &M);
	
	for(i = 0; i < N; i++){
		scanf("%s", in_arr[i]);
		for(j = 0; j < M; j++){
			if(in_arr[i][j] == '*')
				in_arr[i][j] = 1;
			else
				in_arr[i][j] = 0;
		}
	}
	
	for(i=1;i<N-1;i++){
		for(j=1;j<M-1;j++){
			if(in_arr[i][j] == 1){
				k = 1;
				while(i-k >= 0 && j-k >= 0 && i+k < N && j+k < M){
					if(in_arr[i-k][j] && in_arr[i+k][j] && in_arr[i][j-k] && in_arr[i][j+k]){
						pic_arr[i][j] = 1;
						pic_arr[i-k][j] = 1;
						pic_arr[i+k][j] = 1;
						pic_arr[i][j-k] = 1;
						pic_arr[i][j+k] = 1;
						out_arr[i][j]++;
						k++;
						count++;
					}else
						break;
				}
			}
		}
	}
	
	for(i = 0; i < N; i++){
		for(j = 0; j < M; j++){
			if(in_arr[i][j] != pic_arr[i][j])
				count = -1;
		}
	}
	
	printf("%d\n", count);
	
	if(count != -1){
		for(i = 0; i < N; i++){
			for(j = 0; j < M; j++){
				if(out_arr[i][j]){
					for(l = 0; l < out_arr[i][j]; l++){
						printf("%d %d %d\n", i+1, j+1, l+1);
					}
				}
			}
		}	
	}
	
	return 0;
}