[C++] BOJ 18242번 - 네모네모 시력검사

학교에서 진행하는 수업에서 알고리즘 문제를 공유받아 문제를 풀어보았다.

 

문제의 난이도는 실버 5로, 정답률은 약 62%이다. 시간 제한은 1초이다.

문제 링크

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

문제 설명

네모네모 안과에서는 아래와 같은 방법을 이용하여 시력검사를 진행한다.

 

격자가 그려진 흰색 바탕의 N × M 직사각형의 내부에 한 변의 길이가 3보다 큰 홀수이며 행 또는 열에 평행인 단 하나의 정사각형의 테두리를 색칠한다.

 

이때 정사각형의 네 변 중 한 변의 가운데는 색칠하지 않으며 이 색칠하지 않은 변이 정사각형의 어느 변인지를 맞추어 보라는 것으로 시력 검사를 진행한다.

 

예를 들어 N = 7, M = 8 직사각형 내부에 조건에 맞는 다음과 같은 정사각형을 그릴 수 있다.

왼쪽 예제의 경우 색칠하지 않은 변이 오른쪽, 오른쪽 예제의 경우 아래쪽에 있는 것을 알 수 있다.

 

조건에 맞는 입력만 주어질 때, 모든 시력 검사 데이터를 통과하는 프로그램을 작성해보자.

문제 분석

 어느 방향에 구멍이 뚫려있는지 확인하면 되기 때문에 색칠한 네모의 minX, minY, maxX, maxY를 구한 후, 구멍이 뚫린 곳을 찾아내면 문제를 해결할 수 있다.

문제 풀이

 문제에서 값을 입력받을 때에 먼저 minX, minY, maxX, maxY를 찾을 수 있도록 입력을 받았다. 그리고 색칠된 네모의 width와 height를 구한 후, 각각 상단, 좌측, 우측, 하단 가운데가 색칠이 되어있는지 확인하여 답을 출력하였다.

 

전체 코드는 아래와 같다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;

    cin >> N >> M;

    vector<vector<char>> map(N, vector<char>(M)); // map[N][M] N이 height, M이 width

    int minX, minY, maxX, maxY;

    bool isFirstSharp = false;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == '#' && isFirstSharp == false)
            {
                minY = i;
                minX = j;
                isFirstSharp = true;
            }
            else if (map[i][j] == '#')
            {
                maxY = i;
                maxX = j;
            }
        }
    }

    const int width = maxX - minX;
    const int height = maxY - minY;

    if (map[minY][minX + width / 2] == '.')
        cout << "UP" << '\n';
    if (map[maxY][minX + width / 2] == '.')
        cout << "DOWN" << '\n';
    if (map[minY + height / 2][minX] == '.')
        cout << "LEFT" << '\n';
    if (map[minY + height / 2][maxX] == '.')
        cout << "RIGHT" << '\n';

    return 0;
}