파이썬 박스(백준 BOJ 9455)
문제
m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.
그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.
박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.
출력
각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.
예제 입력 1
3
5 4
1 0 0 0
0 0 1 0
1 0 0 1
0 1 0 0
1 0 1 0
3 3
1 1 1
1 1 1
0 0 0
5 6
1 0 1 1 0 1
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 1 0 1 0 1
예제 출력 1
8
6
16
📝 풀어보기
📌 이 문제에는 크게 3가지의 조건이 있다.
- 현재 박스 아래에는 박스가 없어야 한다.
- 박스는 바닥을 벗어나면 안된다. -> 리스트의 범위를 벗어나면 안된다.
- 박스를 이동할 때에는 현재 위치는 0으로 저장되고 아래 위치는 1로 저장한다.
📌 먼저 테스트 케이스를 입력받고 T만큼 반복하면서 N, M (행과 열)을 입력받는다.
그리고 박스들의 움직임을 표현할 2차원 리스트를 생성하고 박스가 있는 공간, 빈 공간, 움직임을 확인할 수 있게 변수를 생성한다.
T = int(input())
for _ in range(T):
N, M = map(int, input().split()) # N 행 M 열
box_list = [list(map(int, input().split())) for _ in range(N)]
box = 1
empty = 0
move = 0
📌 열과 행의 역순(아래에서 위로)을 탐색하며 탐색중인 좌표에 박스가 있으면 조건에 따른 실행을 하도록 한다.
그리고 박스가 있던 위치를 0으로 바꾸고 박스가 아래로 이동했으므로 이동한 자리는 1로 변경한다. break될 때 까지 y를 증가시키면서 이동값을 누적하고 출력한다.
# 2중 반복문
# 열부터 순환
for x in range(M): # 열(row) 개수
# 행순회, 단 아래에서 위로 탐색을 한다.
for y in range(N-1,-1,-1): # 4 3 2 1 0
# 만약에 현재 탐색하고 있는 좌표에 박스가 있으면
if box_list[y][x] == box:
while True:
# 조건1. 현재 박스 아래에 박스가 없어야 한다.
if y+1 == N:
break
# 조건2. 박스가 바닥을 벗어나면 안된다.
if box_list[y+1][x] == box:
break
box_list[y][x] = empty
box_list[y+1][x] = box
y += 1
move += 1
print(move)
전체 코드
# 1. 현재 박스 아래에 박스가 없어야 한다.
# 2. 박스는 바닥을 벗어나면 안된다. -> 리스트의 범위를 벗어나면 안된다.
# 3. 박스이동 -> 현재 위치는 0 저장, 아래 위치는 1 저장
T = int(input())
for _ in range(T):
N, M = map(int, input().split()) # N 행 M 열
box_list = [list(map(int, input().split())) for _ in range(N)]
box = 1
empty = 0
move = 0
# 2중 반복문
# 열부터 순환
for x in range(M): # 열(row) 개수
# 행순회, 단 아래에서 위로 탐색을 한다.
for y in range(N-1,-1,-1): # 4 3 2 1 0
# 만약에 현재 탐색하고 있는 좌표에 박스가 있으면
if box_list[y][x] == box:
while True:
# 조건1. 현재 박스 아래에 박스가 없어야 한다.
if y+1 == N:
break
# 조건2. 박스가 바닥을 벗어나면 안된다.
if box_list[y+1][x] == box:
break
box_list[y][x] = empty
box_list[y+1][x] = box
y += 1
move += 1
print(move)