[에드혹] 오락실에 간 총총이 (26071)(C++)

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

26071번: 오락실에 간 총총이

 

1. 문제 개요

 

게임의 화면은 NxN 크기의 칸으로 나누어져 있고, 각 칸에는 곰곰이가 있거나 또는 비어있다. 화면에는 최소 한 마리의 곰곰이가 존재한다.

게임은 상하좌우 네 개의 버튼을 눌러서 진행할 수 있다. 각 버튼을 누르게 되면, 화면에 있는 모든 곰곰이들이 그 버튼에 해당하는 방향으로 한 칸 움직이게 된다. 만약 이미 화면의 끝에 있어서 그 방향으로 이동하지 못하는 곰곰이들은 가만히 있는다. 버튼을 잘 눌러서 모든 곰곰이들을 하나의 칸에 모으게 되면, 승리하게 된다. 승리하기 위해, 최소 몇 번의 버튼을 눌러야 게임을 클리어할 수 있는지를 구해보자.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

NxN 크기의 칸에서 모든 곰곰이를 한 칸으로 모으는 최소 값을 구하는 문제이다. 상하좌우 버튼을 누를 수 있고 버튼을 누를 시에는 모든 곰곰이가 움직인다. 버튼을 누를 때마다 모든 곰곰이가 같이 움직이기 때문에 다른 칸에 있는 곰곰이가 둘 이상인 경우에는 곰곰이를 모을 수 있는 칸이 중앙에 위치할 수 없고 가장자리에 위치할 수 밖에 없다. 곰곰이를 한칸에 모을 수 있는 경우의 수는 크게 세 가지가 있다.

 

첫 번째로는, 화면에 하나의 곰곰이만 있는 경우이다. 이 경우에는 버튼을 누르지 않아도 되므로 최소값이 0이 된다.

 

두 번째로는, 모든 곰곰이들이 같은 열이나 같은 행에 있는 경우이다. 이 경우에는 상하좌우 중에 하나의 키만 누르면 곰곰이들이 하나의 칸으로 모일 수 있게 된다. 아래 사진의 경우가 이에 해당된다. 

 

위의 경우에는 왼쪽으로만 두 번 움직여서 곰곰이들을 한 칸에 모을 수 있다.

세 번째 경우는 위의 두 경우를 제외한 경우가 된다. 상하, 좌우 중의 조합을 사용해서 오른쪽 위, 왼쪽 위, 오른쪽 아래, 왼쪽 아래, 네 칸 중 하나로 모을 수 있다.

세 번째 경우에는 위의 네 개의 칸 중에서 가장 눌러야하는 버튼이 적은 구석으로 곰곰이들을 모은 것이 정답이 된다.

 

눌러야하는 버튼의 수를 계산하는 방법은 각 칸에서 가장 멀리 떨어져 있는 곰곰이를 기준으로 계산하면 된다. 예를 들어, 아래의 사진에서는 왼쪽 위 모서리에서 가장 멀리 떨어져있는 곰곰이를 기준으로 하는 경우 왼쪽으로 3칸, 위로 3칸 움직여야 하므로 총 눌러야하는 버튼의 수가 6번이 된다. 

 

따라서, 곰곰이들 좌표값으로 minX, minY, maxX, maxY를 구한 후에 이 값을 사용하여 네 칸의 모서리로 곰곰이들을 옮기려면 눌러야하는 버튼 수를 구한 후에 이 값 중에서 제일 작은 값을 정답으로 선택하면 된다.

 

 

4. 전체 코드

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    
    int vMax = 0, hMax = 0, vMin = 1500, hMin = 1500;
    
    for(int i=0;i<N;i++) {
        string temp;
        cin >> temp;
        for(int j=0;j<N;j++) {
            if(temp[j]=='G') {
                if (i > hMax) hMax = i;
                if (i < hMin) hMin = i;
                if (j > vMax) vMax = j;
                if (j < vMin) vMin = j;
            }
        }
    }
    
    int ans = 0;
    
    N -= 1;
    
    if(hMax==hMin && vMax==vMin)
        ans = 0;
    else if(hMax==hMin)
        ans = min(vMax,N-vMin);
    else if(vMax==vMin)
        ans = min(hMax,N-hMin);
    else
        ans = min(min(vMax+hMax,N-vMin + N-hMin),min(vMax+N-hMin,hMax+N-vMin));
    
    cout << ans;

}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!