SW Expert Academy 13732_정사각형 판정 문제풀이 in C++

2022년 10월 26일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

SWEA : 13732_정사각형 판정

문제 요구사항

---

• N×N 크기의 격자판이 있다. 각각의 격자는 비어 있거나(‘.’), 막혀 있다(‘#’). 이때, 막혀 있는 칸들이 하나의 정사각형을 이루는지를 판단하는 프로그램을 작성하라.

[입력]

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스의 첫 번째 줄에는 격자판의 크기 N (1≤N≤20 이 주어진다.
• 다음 N개의 줄은 격자판의 배치를 나타내며, 각 줄에는 ‘.’ 또는 ‘#’로만 이루어진 길이가 N인 문자열이 주어진다.
• 모든 격자판에는 최소 1개 이상의 ‘#’ 칸이 있음이 보장된다.

[출력]

• 각 테스트 케이스마다 격자판의 막혀 있는 칸들이 하나의 정사각형을 이루면 ‘yes’를, 그렇지 않다면 ‘no’를 출력한다.

접근 방법

---

• 문제를 잘못 이해해서 BFS로 접근했다. 문제에 나와있는 TC 2번을 보면 ‘#’이 각각 1개씩 네 군데에 떨어져있는데, 이게 나는 문제에서 원하는 정사각형 하나가 아닌 4개여서 틀렸다고 판단하고 문제를 풀었는데 아니었다.
• 문제에서 요구하는 것은 ‘#’이 나오게 되면 그게 바로 사각형의 시작점이 된다. 그럼 그 후로 나오는 ‘#’들을 이었을 때 이게 정사각형이냐를 판별하는 문제였다.
• 즉, BFS로 굳이 풀 필요 없다. 탐색만으로 충분히 가능하다

풀이 순서

---

1. TC를 입력받아 해당 TC만큼 test_case를 반복한다.
2. N을 입력받고, N 크기만큼의 맵 정보를 입력 받는다.
3. 맵을 탐색하며, ‘#’이 나왔을 때 사각형의 좌상단 좌표, 우하단 좌표를 min, max 함수를 이용해서 찾는다.
4. 해당 좌표를 x2 - x1 값과 y2 - y1의 값이 같지 않다면 false ( no 출력)을, 같다면 x1부터 x2까지, y1부터 y2까지 for문을 돌려 빠짐없이 ‘#’으로 채워졌는지 확인한다. 안 채워져있다면 return false
5. 앞 조건식에서 return 되지 않고 진행됐다면 return true를 한다.

소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
char map[20][20] = { 0, };

bool checkSquare(vector<pair<int,int>> v) {
	int left_x = v[0].first, left_y = v[0].second;
	int right_x = v[1].first, right_y = v[1].second;

	if (right_x - left_x != right_y - left_y) 
		return false;

	for (int i = left_x; i <= right_x; i++) {
		for (int j = left_y; j <= right_y; j++) {
			if (map[i][j] != '#')
				return false;
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int TC;
	cin >> TC;

	for (int test_case = 1; test_case <= TC; test_case++) {
		cin >> N;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
			}
		}
		vector<pair<int, int>> p(2);
		p[0].first = N;
		p[0].second = N;
		p[1].first = -1;
		p[1].second = -1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == '#') {
					p[0].first = min(p[0].first, i);
					p[0].second = min(p[0].second, j);
					p[1].first = max(p[1].first, i);
					p[1].second = max(p[1].second, j);
				}
			}
		}

		if (checkSquare(p))
			cout << "#" << test_case << " yes\n";
		else
			cout << "#" << test_case << " no\n";

	}

	return 0;
}

문제 풀이 결과

---