백준 1652번 - 누울 자리를 찾아라

일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.

코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.)

만약 방의 구조가 위의 그림처럼 생겼다면, 가로로 누울 수 있는 자리는 5개이고, 세로로 누울 수 있는 자리는 4개 이다. 방의 크기 N과 방의 구조가 주어졌을 때, 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 수를 구하는 프로그램을 작성하시오.

 

문제는 장황하지만 연속으로 빈공간이 2칸이상인 구역의 수를 가로와 세로 각각 구하면 문제를 해결할 수 있다. 

여기서 고려해야할 점은 양옆으로 쭉 뻗으면서 눕는다는 내용인데 필자는 처음에 이말이 무슨 말인지 이해하지 못했는데 뒤에 벽이나 짐에 닿게 된다 라는 내용을 고민해보니 간신히 이해했다. 

몸을 양 옆으로 뻗으면 반드시 벽이나 짐이 닿는다 했으므로 위 예시의 3번쨰 가로줄은 하나의 누울자리로 취급된다.

해당 줄에서 어느 자리에 눕던지 몸을 쭉뻗어 벽에 닿게 되기 때문이다.

 

따라서 가로줄과 세로줄별로 한줄씩 따라가면서 장애물이나 벽을 만날 때 비어있는 자리가2칸 이상인 구역을 세면되는 생각보다 간단한 문제였다.

 

소스코드는 다음과 같다

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>

using namespace std;

int length;
int map[100][100];

int cal_horizon() {
	int count = 0;
	int result = 0;
	for (int i = 0; i < length; i++) {
		count = 0;
		for (int j = 0; j < length; j++) {
			if (map[i][j] == 0) {
				count++;
			}
			else{
				if (count >= 2) {
					result++;
				}
				count = 0;
			}
		}
		if (count >= 2) {
			result++;
		}
	}
	return result;
}

int cal_vertical() {
	int count = 0;
	int result = 0;
	for (int i = 0; i < length; i++) {
		count = 0;
		for (int j = 0; j < length; j++) {
			if (map[j][i] == 0) {
				count++;
			}
			else {
				if (count >= 2) {
					result++;
				}
				count = 0;
			}
		}
		if (count >= 2) {
			result++;
		}
	}
	return result;
}

void debug() {
	for (int i = 0; i < length; i++) {
		for (int j = 0; j < length; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
}
int main()
{
	int result1, result2;
	char info;
	scanf("%d", &length);
	getchar();
	for (int i = 0; i < length; i++) {
		for (int j = 0; j < length; j++) {
			scanf("%c", &info);
			if (info == '.')
				map[i][j] = 0;
			else
				map[i][j] = 1;
		}
		getchar();
	}
	
	//debug();
	printf("%d %d", cal_horizon(), cal_vertical());
}