코드 포스 (Code Forces) - Manhattan Circle (C++)

 

 

.과 #으로 이루어진 2차원의 배열이 주어진다. 행의 길이는 n이며, 열의 길이는 m이다.

좌측상단의 좌표는 (1,1)이며, 우측 하단의 좌표는 (n, m)이다.

 

이 그리드 안에는 맨해튼 원이 존재한다. 맨해튼 원의, 중심을 (h, k)라고 하자.

이 때, (a, b)의 좌표를 지닌 점이, |h - a| + |k - b| < r 을 만족한다면 (a, b)는 맨해튼 원의 내부에 있는 것이다.

 

맨해튼 원의 내부에 속한 점을 #로 표시한 2차원 배열이 주어졌을 때, 맨해튼 원의 중심 좌표를 구하여 출력하면 된다.

 

문제 풀이

문제 해결은 간단하다.

가장 좌측의 점과 우측의 점 혹은 가장 상단의 점과 하단의 점을 구하면 된다.

 

맨해튼 원을 그려보면, 항상 마름모의 꼴을 나타내고 해당 마름모는 중심점을 기준으로 대칭을 이룬다.

또한, 원의 중심을 지나며 x축과 수평인 직선에 대해서도 대칭이며, 원의 중심을 지나며 y축과 수평인 직선에 대해서도 대칭을 이룬다.

 

맨해튼 원 내부의 점중 가장 좌측에 있는 점과 가장 우측에 있는 점 또한 원의 중심점을 기준으로 대칭을 이룬다.

그렇다면, 맨해튼 원 내부의 점중 가장 좌측에 있는 점과 우측에 있는 점의 중심점이 원의 중심이 될 것이다. 

 

풀이 코드

int Height = 0;
int Width = 0;

std::cin >> Height >> Width;

먼저, 배열의 행과 열의 크기를 입력받아주자.

std::pair<int, int> LeftPos = { 9999999,9999999 };
std::pair<int, int> RightPos = { -9999999, -9999999 };

맨해튼 원 내부의 점중 가장 좌측에 있는 점과 우측에 있는 점을 구하기 위해 선언해주자.

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        char Input = 0;
        std::cin >> Input;

        if (Input == '#')
        {
            if (LeftPos.second > j)
            {
                LeftPos = { i, j };
            }

            if(RightPos.second < j)
            {
                RightPos = { i, j };
            }
        }
    }
}

입력을 받아 주면서, 현재 좌표에 대해 LeftPos와 RightPos를 계속 갱신해주자.

std::pair<int, int> Answer = { LeftPos.first + RightPos.first + 2, LeftPos.second + RightPos.second + 2};

Answer.first /= 2;
Answer.second /= 2;

최종적으로 구해진 leftPos와 RightPos의 중심점을 구해주자.

 

(첫번쨰 줄을 보면, LeftPos.first + RightPos.first에 2를 추가로 더해주고 있는데, 정답으로 출력될 좌표는 (1,1)을 시작으로 하기 때문에 각 좌표에 1씩 더해준 것이다.)

std::cout << Answer.first << " " << Answer.second << "\n";

구한 정답을 출력해주면 된다.

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    for (int Case = 0; Case < NumCase; Case++)
    {
        int Height = 0;
        int Width = 0;

        std::cin >> Height >> Width;

        std::pair<int, int> LeftPos = { 9999999,9999999 };
        std::pair<int, int> RightPos = { -9999999, -9999999 };

        for (int i = 0; i < Height; i++)
        {
            for (int j = 0; j < Width; j++)
            {
                char Input = 0;
                std::cin >> Input;

                if (Input == '#')
                {
                    if (LeftPos.second > j)
                    {
                        LeftPos = { i, j };
                    }

                    if(RightPos.second < j)
                    {
                        RightPos = { i, j };
                    }
                }
            }
        }

        std::pair<int, int> Answer = { LeftPos.first + RightPos.first + 2, LeftPos.second + RightPos.second + 2};
        
        Answer.first /= 2;
        Answer.second /= 2;

        std::cout << Answer.first << " " << Answer.second << "\n";
    }


    return 0;
}