[백준] 1652번 누울 자리를 찾아라 C++ 풀이

---

알고리즘 분류

• 구현
• 문자열

---

문제 설명

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

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

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

---

입력 설명

첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100 이하의 정수이다. 그다음 N 줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다.

---

출력 설명

첫째 줄에 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 개수를 출력한다.

---

예제 입력

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

---

예제 출력

5 4

---

아이디어

가로로 측정하고 세로로 측정해서 출력한다.

---

알고리즘

가로로 쭉 가면서 .이 나오면 count를 증가시키고 x가 나왔을 때 cnt가 2 이상이면 가로 count를 증가시킨다.

만약 마지막줄까지왔는데 x가 나온 적이 없다면 cnt가 2 이상인지 체크해서 가로 count를 증가시킨다.

동일하게 세로도 반복한 후 가로 세로 count를 출력한다.

---

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	int n;
	cin>>n;
    vector<string> arr(n);
	for(int i=0; i<n; i++)
		cin>>arr[i];
	int ga=0, se=0;
	for(int i=0; i<n; i++)
	{
		for(int j=0,cnt=0; j<n; j++)
		{
			if(arr[i][j] == '.')
			{
				cnt++;
                if(j==n-1 && cnt >= 2) ga++;
			}
			else
			{
				if(cnt >= 2) ga++;
                cnt=0;
			}
		}
	}
	for(int i=0; i<n; i++)
	{
		for(int j=0,cnt=0; j<n; j++)
		{
			if(arr[j][i] == '.')
			{
				cnt++;
                if(j==n-1 && cnt >= 2) se++;
			}
			else
			{
				if(cnt >= 2) se++;
                cnt=0;
			}
		}
	}
	cout<<ga<<" "<<se;
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1652

처음에는 문제가 이해가 안 갔다.

왜 저 예시에서 가로가 5고 세로가 4인지 몰랐다.

힌트를 보고 나서야 영식이의 몸은 빈칸만큼 계속 늘어날 수 있다는 것을 알았다.

만약 빈칸이 연속으로 5칸이 있다면 영식이의 몸은 5칸만큼 늘어나는 식이다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!