🙇‍♀️[Silver III] 숫자 정사각형 - 1051

문제 링크

성능 요약

메모리: 2036 KB, 시간: 0 ms

분류

브루트포스 알고리즘, 구현

제출 일자

2023년 12월 25일 14:08:32

문제 설명

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

🚀풀이

보드를 처음부터 끝까지 순회하면서 최댓값을 찾아야한다.

한 위치에 왔을 떄 해야하는 일은 다음과 같다.

  1. 그 위치에서 오른쪽 방향으로 스캔을 시작한다.
  2. 자신과 같은 숫자가 나오면 그 위치와 시작 위치의 차이를 구한다.
  3. 시작 위치와 현재 위치에서 y축 방향으로 차이만큼 이동해서 같은 숫자인지 확인한다.
  4. 기존의 값보다 크면 값을 갱신한다.

이렇게 생각을 하고 구현을 하니 3중 for문이 나왔다.

보드의 y, x의 최댓값이 50이므로 시간 제한이 나오지 않을거같아서 그냥 했다.

void solve()
{
	// 로직의 순서
	// 보드의 처음부터 끝까지 순회를 할거임
	// 한 위치에서 해야하는 일
	// 1. 그 위치에서 오른쪽 방향으로 스캔시작 (범위 생각)
	// 2. 자신과 같은 숫자가 나오면 그 차이만큼 해당위치에서 아래로 이동해서 확인 (범위체크 필요)
	// 3. 자신의 위치에서도 같은 역할 수행
	// 4. 기존의 값보다 크면 값 갱신

	for (int y = 0; y < n; ++y)
	{
		for (int x = 0; x < m; ++x)
		{
			int cur = board[y][x];
			for (int i = x; i < m; ++i) // 오른쪽 방향으로 스캔 시작
			{
				if (board[y][i] == cur) // 같은 숫자가 나온경우
				{
					int dist = i - x;

                    // 범위에서 벗어나지 않고 아래로 이동했을 때 같은 숫자인경우
					if (y + dist < n && board[y + dist][x] == cur && board[y + dist][i] == cur)
					{
                        // 값 갱신하기
						res = max(res, (dist + 1) * (dist + 1));
					}
				}
			}
		}
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, res = 1;
int board[52][52];

void setting()
{
	cin >> n >> m;

	string str;
	for (int y = 0; y < n; ++y)
	{
		cin >> str;
		for (int x = 0; x < m; ++x)
		{
			board[y][x] = str[x] - '0';
		}
	}
}

void solve()
{
	// 로직의 순서
	// 보드의 처음부터 끝까지 순회를 할거임
	// 한 위치에서 해야하는 일
	// 1. 그 위치에서 오른쪽 방향으로 스캔시작 (범위 생각)
	// 2. 자신과 같은 숫자가 나오면 그 차이만큼 해당위치에서 아래로 이동해서 확인 (범위체크 필요)
	// 3. 자신의 위치에서도 같은 역할 수행
	// 4. 기존의 값보다 크면 값 갱신

	for (int y = 0; y < n; ++y)
	{
		for (int x = 0; x < m; ++x)
		{
			int cur = board[y][x];
			for (int i = x; i < m; ++i)
			{
				if (board[y][i] == cur)
				{
					int dist = i - x;

					if (y + dist < n && board[y + dist][x] == cur && board[y + dist][i] == cur)
					{
						res = max(res, (dist + 1) * (dist + 1));
					}
				}
			}
		}
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고