[Silver V] 2563번: 색종이 (C++, 구현)

이번에 풀 문제

 

본문을 작성하는 사람은 주로 C++을 사용합니다.

---

1. 문제 개요

 1-1. 시나리오

문제

 1-2. 입력

입력

 1-3. 출력

  색종이가 붙은 검은 영역의 넓이를 출력한다.

 

 1-4. 문제 링크

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

2563번: 색종이

 

---

2. 풀이

 2-1. 문제 이해

 일단.. 문제를 먼저 이해 해 봐야겠지요.

입력으로 들어오는 숫자를 먼저 이해 해 보도록 합시다.

🎈 입력
1
3 7

 

위와 같은 입력이 들어왔다면. 한줄 한 줄 번역했을 때

1 : 색종이 1장을 쓰겠다.

3 7 : 왼쪽부터 3칸, 아래로부터 7칸 거리에 있는 색종이가 있다.

 

3 7을 한번 그려볼까요?

좌 3, 하 7의 위치에 찍힌 점

 

왼쪽으로부터 3간, 아래로부터 7칸 거리 위치에 점을 찍었습니다.색종이의 크기는 10x10이라 했으니, 찍힌 점의 위치를 색종이의 좌측 하단 끝점이라고 정의한다면

1번 색종이

박스 쳐진 부분이 색종이가 됩니다.색종이의 크기는 10x10이니, 캔버스에 올라간 색종이의 넓이는 100이 됩니다.

 

 

만약 두개의 색종이가 위 사진처럼 겹쳐지게 된다면,색종이의 넓이가 200이 아니라, 150이 되겠죠.색종이의 개수를 구하는게 아니라, 캔버스에 올라간 개수를 구하는 것 이니까요.

 

이런 식으로 주어지는 모든 색종이를 그렸을 때, 100x100의 캔버스 위에 올라간 색종이의 넓이를 구하는 문제입니다.

추후 더 설명을 보완해서 수정해보도록 하죠.

 

 

자.. 그럼 이해가 되었으니, 코드를 짜 보도록 합시다.

 

 2-2. 코드 작성

 우선, 저같은 경우 C++ 컨테이너 중 하나인 벡터 자료구조를 통해 문제를 해결했습니다.

100x100의 캔버스를 2차원 배열로 만들었고, 색종이가 올라간 부분을 특정한 뒤 개수를 구하는 방법을 사용했죠.

 

우선.. 배열을 선언 해 주도록 합시다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<vector<bool>> m_whiteboard(100);
	for (int i = 0; i < 100; i++) {
		m_whiteboard[i].resize(100, false);
	}
}

 

vector<vector<bool>> m_whiteboard(100);

을 통해 2차원 bool 배열을 선언했고, 먼저 1차원의 배열 개수를 100개로 설정 해 주었습니다. (세로 길이 지정)

그 다음, for문을 통해 가로 길이(2차원 배열)의 길이를 각각 100개로 설정 해 주었습니다.

 

이렇게 한다면, 대충 이런 배열이 만들어집니다..

오메 눈 아픈거

잘 안 보이네..

 

조금 확대하면 이렇게 보입니다.

100x100. 즉 10,000개의 공간을 가진 거대한 Vector 배열이 만들어졌습니다.

우린 이 배열에 색종이를 얹을겁니다.

 

먼저, 색종이의 수를 입력받고,

색종이 수 만큼 반복하는 반복문을 만들어 줍시다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int m_paper_count;
    
    	cin >> m_paper_count;

	while (m_paper_count != 0)
	{
    		int x, y;
		cin >> x >> y;
        
    		m_paper_count--;
	}
}

 

반복문 속에서 x와 y값까지 받아냅니다.

이 값은 왼쪽으로부터 떨어진 거리, 아래로부터 떨어진 거리를 입력받기 위한 겁니다.

 

그 다음은 간단합니다.

주어진 x와 y의 위치에서 10x10의 공간을 모두 "채워졌다" 라고 설정 해 주기만 하면 됩니다.

주어진 위치가 색종이의 중간지점이라던지, 그런 것이 아니기 때문에

x의 위치에서부터 10칸, y의 위치에서부터 10칸인 공간을 검색하여 비어있다면 채워주기만 하면 됩니다.

	int m_paper_count;
	int area = 0;
    
    	cin >> m_paper_count;

	while (m_paper_count != 0)
	{
		int x = 0, y = 0;
		cin >> x >> y;

		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				if (!m_whiteboard[y + i][x + j])
				{
					m_whiteboard[y + i][x + j] = true;
					area++;
				}
			}	
		}

		m_paper_count--;
	}

 

m_paper_count는 색종이의 수.

area 변수는 색종이의 넓이 값을 의미합니다.

 

배열 아이템을 검색했을 때, 그 공간이 비어있다(겹쳐있지 않다) 면

area 변수의 값을 증가시킵니다.

 

 

자. 다 됐습니다.

area 변수값만 표출 해 주면 해결~

그 전에, 예시로 주어지는 입력을 넣어봅시다.

입력과 출력

 

이제, "1"로 표현 된 (True) 공간의 개수를 모두 더한 값을 표현만 해 준다면?

성공!

성공

 

= 코드 전문 =

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int m_paper_count;
	int area = 0;

	vector<vector<bool>> m_whiteboard(100);
	for (int i = 0; i < 100; i++) {
		m_whiteboard[i].resize(100, false);
	}

	cin >> m_paper_count;

	while (m_paper_count != 0)
	{
		int x = 0, y = 0;
		cin >> x >> y;

		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				if (!m_whiteboard[y + i][x + j])
				{
					m_whiteboard[y + i][x + j] = true;
					area++;
				}
			}	
		}

		m_paper_count--;
	}

	cout << area;
}

 2-2. Github

https://github.com/devbini/Algorithm/tree/ac5ee9a4437a6dffe46d860c5bdeeb16de961ee2/%EB%B0%B1%EC%A4%80/Silver/2563.%E2%80%85%EC%83%89%EC%A2%85%EC%9D%B4

---

 

3. 기억해 둘 부분

이것도 백터 컨테이너 활용, 조금 무식하게 푼 경향이 분명히 있다.

조금 더 보다가 다른 방법이 생각나면 추가로 글을 쓰도록 하겠다.

 

요즘 코딩테스트를 잘 안 하는 추세인 것 같다..

나온다 해도 <구현> 은 잘 나오는 분야중 하나이니, 열심히.. 해 보도록 하자.

문제를 이해하는 능력을 매우 요구한다!

 

아, 처음에는

아래 코드처럼 마지막에 area 개수 검사를 따로 했었다ㅋㅋ

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int m_paper_count;

	vector<vector<bool>> m_whiteboard(100);
	for (int i = 0; i < 100; i++) {
		m_whiteboard[i].resize(100, false);
	}
	
	cin >> m_paper_count;

	while (m_paper_count != 0)
	{
		int x = 0, y = 0;
		cin >> x >> y;

		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				m_whiteboard[y + i][x + j] = true;
			}	
		}

		m_paper_count--;
	}

	int area = 0;
	for (int i = 0; i < 100; i++)
	{
		for (int j = 0; j < 100; j++)
		{
			if (m_whiteboard[i][j]) area++;
		}
	}

	cout << area;
}

문제 자체는 통과하지만, 불필요한 코드는 최대한 최적화 시켜버리도록 하자.

메모리는 거의 동일하게 사용했지만.. 코드길이(Byte)가 줄어들었다. 히히.