C++ / 1652 / 누울 자리를 찾아라 ( 문자열 )

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

문제 요약

코레스코 콘도에 있는 방은 n * n 정사각형모양으로 생겼습니다. 방 안에는 옮길 수 없는 짐들이 많이 있어서 영식이의 누울 자리를 차지하고 있었습니다.

영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 합니다.

영식이가 누울 수 있는 자리에는 조건이 있습니다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있습니다. 가로로 누울 수도 있고 세로로 누울 수도 있습니다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 집에 닿게 됩니다. ( 중간에 어정쩡하게 눕는 경우는 없습니다. )

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

 

'.'은 아무것도 없는 곳, 'X'는 짐이 있는 곳을 의미합니다.

문제 풀이

1. 방을 입력받을 2차원 배열과 자리 개수를 가로, 세로로 입력받을 변수 2개와 빈칸을 세어줄 변수를 만듭니다.

2. 방 구조를 입력받습니다.

3. 가로로 먼저 탐색을 하는데 빈칸 ( ' . ' )이 나오면 빈칸을 세어줍니다.

4. 빈칸이 2개가 되면 자리 개수를 세어주고, 짐이 있는 칸이 나오면 빈칸 세는 변수를 초기화 해줍니다.

5. 세로로도 똑같이 반복문을 돌립니다.

6. 가로의 자리 개수와 세로의 자리 개수를 출력합니다.

주의할 점

처음 코드를 작성할때는 단순하게 세로든 가로든 빈칸이 2칸일 경우에 탐색을  멈추고 개수를 세었었는데 그렇게 하면

.	.	x	.	.
.	.	x	.	.
x	x	x	x	x
.	.	x	.	.
.	.	x	.	.

같은 경우에 실제 누울 수 있는 자리는 8, 8 이 나와야 하지만 4, 4가 나오는 예외가 생겼습니다.

그래서 2칸이 되자마자 탐색을 멈추게 하면 안되고 2칸이 되었을때만 자리의 수를 더하도록 해야합니다.

코드

#include<iostream>
#include<vector>

using namespace std;

vector<vector<char>>v;
int n, a =0, b=0, cnt=0;
int main()
{
	cin >> n;
	v.resize(n, vector<char>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> v[i][j];
		}
	}

	// 가로 누울 자리
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (v[i][j] == '.')
			{
				cnt++;
				if (cnt == 2)
				{
					a += 1;
				}
			}
			else
			{
				cnt = 0;
			}
		}

		cnt = 0;
	}
	cnt = 0;

	// 세로 누울 자리
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (v[j][i] == '.')
			{
				cnt++;
				if (cnt == 2)
				{
					b += 1;
				}
			}
			else
			{
				cnt = 0;
			}
		}

		cnt = 0;
	}


	cout << a << " " << b;
	return  0;
}

반응형

예제 1

5
....X
..XX.
.....
.XX..
X....

결과 1

예제 2

5
..X..
..X..
XXXXX
..X..
..X..

결과 2