[BaekJoon] 백준 9455 박스 (Python / 파이썬)

BaekJoon 백준 9455 박스 문제는 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때까지 아래로 움직인다면, 박스는 쌓인 상태가 된다. 모든 박스가 바닥에 쌓이기 전까지 이동한 거리의 합을 구하는 문제이다. 난이도는 Bronze 1이다.

 

BaekJoon 9455 박스 문제 정보

출처

- https://www.acmicpc.net/problem/9455

알고리즘 분류

- 문자열 string, 파싱 parsing, 구현

난이도

- 브론즈 1 / Bronze 1

 

박스 문제 요약

• m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때까지 아래로 움직인다면, 박스는 쌓인 상태가 된다. (1 ≤ m, n ≤ 100)
• 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다.
• 박스가 움직인 거리는 바닥에 쌓이기 전까지 이동한 칸의 개수이다.
• 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합)을 구하여 출력한다.

 

문제 풀이 과정

1. 행이 아닌, 열 별로 박스의 위치를 2차원 리스트에 저장한다.
2. 열 별로 박스의 개수를 구하고 바닥을 행의 개수로 설정한다.
3. 열의 박스의 위치를 역순으로 탐색하며 상자를 만나면 바닥과의 차이(박스의 이동 거리)를 구하여 이동 거리에 합하고, 바닥은 1 높인다.
4. 모든 열을 돌며 2~3 과정을 반복한다.
5. 모든 박스가 이동한 거리를 출력한다.

 

코드 및 설명

• grid [][] - 열 별 상자의 위치를 저장한 이차원 리스트
• moveCnt - 모든 박스가 이동한 거리
• boxNum - 열 별 박스의 개수
• floor - 바닥 위치

for _ in range(int(input())):
    m, n = map(int, input().split())
    grid = [[] for _ in range(n)]
    # 열 별 박스의 위치 저장
    for i in range(m):
        a = list(input().split())
        for j in range(n):
            grid[j].append(a[j])

    moveCnt = 0
    for i in range(n):
        # i열의 박스의 개수
        boxNum = grid[i].count('1')
        floor = m - 1  # 바닥
        
        # 열의 아래부터 박스의 위치 이동
        for j in range(m - 1, -1, -1):
            # 박스를 제 자리에 놓고 바닥을 1 높인다.
            if grid[i][j] == '1':
                moveCnt += floor - j
                floor -= 1
                
    print(moveCnt)

---

BaekJoon 백준 9455 박스 문제를 파이썬 python으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.