그리드 형식의 값을 다루는 방법

행과 열로 이루어진 데이터를 다뤄야 하는 가장 흔한 경우는 DB의 조회 결과를 다루거나 CSV 파일을 다룰 때이다. 이 경우에 각각의 행은 필드값들이 연속된 리스트이며, 전체 데이터 테이블은 개별 행(리스트)이 중첩된 2중 리스트 구조를 갖는다.

하지만 이런 케이스들은 모두 "테이블" 형태의 데이터를 다루고 있다. 즉 대부분의 처리는 각 행 혹은 라인에 대해 반복하면서 특정한 작업을 처리한다. 그러다보니 대부분 그리드 형식의 데이터를 다루는 경우에 아무런 거리낌없이 2중 리스트를 사용하고 있는데, 개인적으로 "테이블" 형식의 데이터가 아닌 단순 그리드에 대해서는 2중 리스트를 사용하는 것을 그리 좋아하지 않는다.

이 글에서는 그리드의 데이터를 단일 리스트를 사용하여 다루는 기법에 대해서 알아보겠다.

그리드 형식 데이터 문제

1~3자리 정수가 20개씩 20행에 나열된 다음과 같은 데이터가 파일에 저장되어 있다고 하자.

114 127 120 033 077 176 029 101 078 113 004 190 074 114 024 076 064 120 106 199
186 092 198 134 051 168 131 165 165 087 078 068 145 112 049 193 054 079 041 065
094 085 065 097 081 185 059 064 183 134 194 196 175 120 180 170 153 076 158 058
040 025 131 185 051 112 108 082 047 156 160 091 145 126 182 126 090 065 165 022
001 074 165 011 094 158 008 074 127 188 122 022 101 160 070 183 140 187 084 060
114 137 162 011 058 104 165 070 042 020 180 145 155 061 193 017 068 194 140 185
025 073 038 130 163 149 063 191 129 061 199 158 091 060 113 141 127 122 093 073
073 103 034 068 092 124 062 015 184 072 132 195 061 191 196 196 030 169 109 096
049 009 064 122 193 036 192 095 018 101 153 170 131 031 035 134 153 074 080 017
169 134 125 087 102 147 066 070 094 093 185 124 123 067 027 179 119 022 001 006
168 050 061 047 083 011 100 119 064 199 086 162 007 029 032 044 197 168 144 130
054 145 112 025 165 063 092 029 189 107 142 022 130 060 139 132 128 098 194 036
046 079 024 039 124 098 173 008 138 010 178 027 030 054 116 140 122 186 012 089
015 044 087 087 138 046 140 134 033 028 084 021 083 109 001 080 144 131 103 167
037 011 116 035 009 108 183 020 113 169 072 146 134 180 168 159 068 008 032 127
180 107 111 138 034 051 056 192 076 067 046 037 155 075 114 078 114 180 054 181
135 199 079 153 104 081 024 095 067 025 166 102 079 010 125 048 098 184 010 068
054 047 031 024 005 134 078 120 020 049 047 193 053 107 054 111 177 128 054 021
040 158 178 106 107 027 168 193 151 072 174 060 052 104 091 105 041 129 053 197
020 085 170 174 146 102 103 029 115 154 164 133 031 144 150 178 020 081 061 112

이때 첫번째 5개의 정수는 114, 127, 120, 33, 77이고 그 합은 471이다. 두 번째 부터 5개의 정수는 127, 120, 33, 77, 176이고 그 합은 533이다. 그리고 이 그리드에서 "한 방향으로 진행하는 5개의 정수"는 오른쪽 직선 방향외에도 아래 방향, 왼쪽 아래 대각선, 오른쪽 아래 대각선으로도 구할 수 있다. 7번째 숫자인 101을 볼 때,

• 오른쪽 방향 다섯 개 : 101, 78, 113, 4, 190
• 아래방향 다섯 개 : 101, 165, 64, 82, 74
• 왼쪽 아래 대각선: 101, 131, 185, 51, 11
• 오른쪽 아래 대각선 : 101, 165, 134, 160, 22

위 와 같이 각각 방향에 따라 4가지 수열이 나올 수 있다. 만약, 이 그리드에서 모든 방향을 고려했을 때 5개 정수값의 합이 최대가 될 때 그 합을 구해보자.

이중 리스트를 사용하는 경우

이 그리드를 2차원 배열로 보고 이중 리스트(리스트의 리스트)로 보는 경우 어떤 식으로 다루게 될까? 아래에 몇 가지 값을 액세스하려는 경우들을 가정해보자.

1. (row, col)에 위치한 단일 값 액세스
2. row 번째 행 액세스
3. col 번째 행 액세스
4. x (= row, col)를 기준으로 오른쪽으로 다섯개 정수
5. x 를 기준으로 아래쪽으로 다섯개 정수
6. x를 기준으로 오른쪽 아래 대각선으로 다섯개 정수
7. x를 기준으로 왼쪽 아래 대각선으로 다섯개 정수

단일 값

(row, col)의 좌표에 위치한 값을 액세스하는 것은 이중 리스트에서는 가장 쉽다. 이중 리스트는 행(row)들의 리스트이므로, value = data[row][col]로 액세스된다.

다만 개인적으로 data[row][col]이라는 표기가 그다지 예쁘게 보이지는 않는다.

row 번째 행 액세스

특정한 행은 data[row]로 액세스할 수 있다.

col 번째 열 액세스

특정한 열은 개별 행의 col 번째 원소들을 모은 것이 되어야 한다. 따라서 [r[col] for r in data]로 구할 수 있다.

여기까진 쉽다.

오른쪽으로 다섯개 정수

특정한 값을 기준으로 오른쪽으로 다섯개 정수를 뽑아내어 보자. 기준값의 위치를 (row, col)이라 할 때, 기준값은 x = data[row][col]이다. 이때 x 가 그리드 폭 - 5 이하여야 한다는 조건이 있다. 어쨌든 단일 리스트인 행에서 특정 열 범위를 얻는 셈이다.

five_r = data[row][col:col+5]

## 오프셋 값을 이용하면
five_r2 = [data[row][col+i] for i in range(5)]

아래쪽으로 다섯개 정수

아래쪽으로 다섯개 내려가는 경우에는 행 번호가 높이 - 5이하여야 한다는 조건이 있다.

five_d = [r[col] for r in data[row:row+5]]

## 오프셋 값을 이용하면
five_d2 = [data[row+i][col] for i in range(5)]

오른쪽 아래 대각선

오른쪽 아래 대각선으로 이어지는 경우 행, 열의 위치가 높이-5, 폭-5 이하여야 한다는 제약이 있다. 오프셋 값을 이용하는 방법만이 존재한다.

five_rd2 = [data[row+i][col+i] for i in range(5)]

왼쪽 아래 대각선. 왼쪽 아래 대각선은 왼쪽으로 진행해야 하기 때문에 열의 위치가 0, 1, 2, 3 인 경우에는 적용될 수 없다는 조건이 있다.

five_ld = [data[row+i][col-i] for i in range(5)]

이상의 케이스들에 대해서 확인하였으니, 5개인접수로 만들어지는 수열의 합의 최대값은 다음과 같이 구할 수 있겠다.

data = []
with open('file.txt') as f:
    for line in f:
        data.append([int(x) for x in line.split()])

result = 0
## 가로 5개씩
for row in range(20):
    for col in range(16):
        s = sum(data[row][col:col+5])
        if result < s:
            result = s

## 세로 5개씩
for row in range(16):
    for col in range(20):
        s = sum(r[col] for r in data[row:row+5])
        if result < s:
            result = s

## 우하단
for row in range(16):
    for col in range(16):
        s = sum(data[row+i][col+i] for i in range(5))
        if result < s:
            result = s

## 좌하단
for row in range(16):
    for col in range(4, 20):
        s = sum(data[row+i][col-i] for i in range(5))

print(s)

문제는 이렇게 합쳐놓고 보면 방향별로 값을 구하는 방법이 제각각이고, 방향별로 row, col의 이중 루프를 도는 식으로 코드가 구성된다. 그렇다면 그리드로 구성하는 경우는 어떨까?

그리드 식 접근법

그리드식 접근법은 주어진 그리드 데이터를 단일 리스트에 다 때려 넣고, 단일 인덱스값으로 특정 위치의 원소를 액세스한다. 기본적으로 특정 원소의 인덱스가 i라고 하면, 그리드로 봤을 때 그 원소의 위치 (row, col)은 다음과 같은 관계를 갖는다.

### 그리드에서의 원소의 위치와 인덱스
### 그리드의 폭을 width, 높이는 height라 가정한다.
### (data의 width=20, height=20)

i = (row * width) + col
### 따라서 
col = i % width
row = i // width

행과 열 액세스

같은 열에 위치한 원소들의 인덱스값은 모두 width만큼씩 떨어져 있다.

row, col = divmod(i, width)
row_at_r = data[row*width:(row+1)*width]
col_at_c = data[col::width]

대각선

서로 이웃한 두 행에서 같은 열의 인덱스끼리는 width 만큼 차이가 난다고 했다. 그렇다면 오른쪽 아래에 있는 원소는 width + 1 만큼의 인덱스차이가 날 것이며, width - 1 만큼의 차이로는 왼쪽 아래가 될 것이다. 즉 방향을 결정하는 것은 건너뛰는 스텝이 되는 것이다.

1. 오른쪽 : +1 씩 진행
2. 아래쪽: +width 씩 진행
3. 우하단 : +width+1 씩 진행
4. 좌하단 : +width- 씩 진행

따라서 최종 코드는 다음과 같이 훨씬 간단하게 정리될 수 있다.

data = []
with open('file.txt') as f:
    data = [int(x) for x in f.read().split()]
width, total = 20, 400

r = max(sum(data[x::1][:5]) for x in range(400) if x % width < 16)
d = max(sum(data[x::width][:5]) for x in range(400) if x // width < 16)
rd = max(sum(data[x::width+1][:5]) for x in range(400)\
          if x % width < 16 and x // width < 16)
ld = max(sum(data[x::width-1][:5]) for x in range(400)\
          4 <= if x % width < 20 and x // width < 16)

result = max((r, d, rd, ld))
print(result)

정리

각 값이 레코드/칼럼으로 구분되는 테이블 형태의 데이터가 아닌 그리드 형식의 데이터를 다뤄야 하는 경우에 있어서, 이중 리스트를 사용하는 것이 언뜻 보기에 개별 값을 액세스하는 것이 간편해 보이기는 하지만, 폭과 높이 정보를 가지고 있으면 충분히 단일 리스트로 다루는 것이 가능하며, 특히 부분열의 계산이 필요한 경우에는 단일리스트로 액세스하는 편이 전체적으로 간결하고 깔끔한 코드를 작성할 수 있다.