[백준 9455번] 박스

문제 설명

m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.

그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.

박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.

출력

각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.

접근 방식 및 풀이

우선 모든 값을 받아서 배열 저장한다.

이제 계산을 해야하는데 박스가 위에서 아래로 떨어지기 때문에 열 단위로 나누어 계산을 할 것이다. 다시 말해서 첫번째 열인 (0,0)부터 (0,m)까지 계산을 하고, 다음열로 넘어가서 (1,0)부터 (1,m)까지 계산을 하는 것이다. 이런 식으로 n개의 열을 차례로 계산하고 합을 출력한다.

그렇다면 하나의 열 내에서 계산은 어떻게 하면 될까? 우선 해당 열의 제일 낮은 칸부터 시작해서 박스가 있는지 확인한다. 만약 박스가 없다면 윗 칸으로 올라간다. 한 칸씩 올라가다가 박스가 있는 칸을 발견하면 해당 박스의 이동 거리만큼(해당 칸의 높이 - 1)을 총 이동 거리에 더한다. 여기서 주의할 점은 같은 열에서 발견한 박스가 많아질수록 아래 깔린 박스가 있어서 이동거리가 줄어든다는 것도 계산해야한다는 점이다. 따라서 두번째 발견한 박스의 이동 거리는 해당 칸의 높이 - 2가 된다.

이런식으로 n개의 열에 대한 계산을 완료하여 나온 값이 모든 박스가 이동한 거리가 된다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>

int main(){
    int testcaseNum, m, n, answer, array[100][100];
    
    scanf("%d", &testcaseNum);

    for(int i = 0; i < testcaseNum; i++){
        scanf("%d %d", &m, &n);
        answer = 0;
        
        for(int j = 0; j < m; j++)
            for(int k = 0; k < n; k++)
                scanf("%d", &array[j][k]);
        
        for(int k = 0; k < n; k++){
            int count = 0;
            
            for(int j = m - 1; j >= 0; j--)
                if(array[j][k] == 1)
                    answer += (m - j) - (++count);
        }
        
        printf("%d\n", answer);
    }
    
    return 0;
}