문제

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

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

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

입력

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

출력

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

박스의 세로줄을 기준으로 박스(1)가 나올 때마다 그 거리를 더해주면 최종 거리가 나온다. 좀 더 효율적인 방법이 없나 생각했는데, 결국은 구현 문제. 각 박스 거리를 일일이 구하는 방법을 효율적으로 짜는 게 관건이다.

처음엔 코드를 매우 복잡하게 지저분하게 짰다. 누가 그랬는데. 읽기 좋은 코드가 좋은 코드라고.

for _ in range(int(input())):
    m, n = map(int, input().split())
    b = []
    for i in range(m):
        l = list(map(int, input().split()))
        b.insert(0, l)
    arr = []
    for j in range(n):
        tmp = []
        for k in range(m):
            tmp.append(b[k][j])
        arr.append(tmp)
    cnt = 0
    for a in arr:
        t = 0
        for idx, num in enumerate(a):
            if num == 1:
                cnt += idx - t
                t += 1
    print(cnt)

딱 봐도 지저분하다. 리스트만 3개나 들어가고, for문도 세 번이나.

간단히 설명하면,

1. 입력되는 숫자를 리스트(l)로 만들어 전체 리스트(b)에 넣되, 나중에 생성되는 리스트가 앞에 오게 만든다. append 대신 insert 메소드를 쓴 이유다. (박스 세로줄을 기준으로 아래부터 읽어나가야 하기 때문에.)
2. 세로줄을 기준으로 리스트를 재배치(arr)한다. (굳이 왜…)
3. 최종 정렬된 리스트(arr)를 반복 순환하며 ‘1’이 나올 때마다 cnt에 추가한다. 1의 인덱스 값에서 앞선 1의 숫자만큼을 빼준다. (그게 움직인 거리니까.)

맞긴 한데, 복잡하고 지저분하다.

좀 더 나은 방법이 없을까. 다른 이들이 올린 코드를 보다가, 더 깔끔한 방법을 찾았다.

for _ in range(int(input())):
    n, m = map(int,input().split())
    box = [input().split() for _ in range(n)] # 전체 리스트 생성
    ans = 0
    for j in range(m):
        cnt = 0
        for i in range(n-1,-1,-1): # 맨 뒤 리스트부터 거꾸로 탐색
            if field[i][j] == '1':
                ans += cnt
            else:
                cnt += 1 # 인덱스 값을 찾는 대신, 0이 나올 때마다 1씩 임시 카운트 값(cnt)을 추가해주면 된다.
    print(ans)

사람은 역시 배워야….

[문제 보기]