blisstoner's profile image

blisstoner

October 20, 2019 09:00

떼껄룩 조각모음

computer vision

이번달 초에 하웨이에서 주최한 마라톤 매치가 있었습니다. 주어진 기간은 2주였고, 1등 상금이 무려 10000달러인 것을 확인하고 눈이 돌아가 얕게 발을 담구었습니다.

이 대회에서 요구한 것은 아래와 같이 8x8조각, 16x16조각, 32x32조각으로 나누어진 고양이 사진을 재배치하는 것이었습니다.

나름대로 프로토타입을 만들고 그럭저럭 괜찮은 점수를 얻었지만 관련 논문들 좀 읽고 ICPC 준비도 하고 그러던 중에 다른 참가자들의 점수가 어떻게 비벼볼 수 없는 수준으로 높아져있는 것을 확인하고 그냥 포기했습니다. 그래도 재밌는 도전이었던 만큼 제가 공부한 기록을 남겨보고 싶어 포스팅을 작성해봅니다.

도전 과제

아래의 그림을 보면 문제가 조금 더 명확하게 이해갈 것입니다.

조각난 고양이 사진

재배치한 고양이 사진

그림은 png 형식이었고 모두 512x512 크기였습니다. 8x8, 16x16, 32x32 조각 각각에 대해 600개는 정답이 주어진 샘플 그림, 300개는 정답을 알려주지 않지만 제출했을 때 스코어를 알려주는 그림, 300개는 정답과 스코어를 전부 알려주지 않고 실제 채점이 진행되는 그림이었습니다.

이 문제는 이미 Computer Vision 분야에서 Square Jigsaw Puzzle이라는 이름으로 연구가 이루어지고 있던 문제입니다.

같이 이 문제를 해결할 방법을 고민해보고, 관련 논문들은 어떤 방식들을 사용하고 있는지 알아봅시다.

인접한 조각 찾기 - RGB

우선 이미지는 numpy와 opencv2 모듈을 이용해 쉽게 처리할 수 있습니다. 직관적으로 생각했을 때 인접한 두 조각은 해당 경계에서 RGB 값이 굉장히 유사할 것입니다. 일단 각 조각에 대해 상하좌우로 인접한 조각을 찾고 나면 그림을 재구성하는 것이 쉬울 것이므로 임의의 두 조각에 대해 상하, 좌우로 배치되었을 때의 점수를 반환하는 두 개의 함수를 만들어보았습니다.

def score1_row(img1, img2, p):
  tot = 0
  for i in range(p):
    for c in range(3):
      tot += (int(img1[i][p-1][c]) - int(img2[i][0][c]))**2
      
  return tot

def score1_col(img1, img2, p):
  tot = 0
  for i in range(p):
    for c in range(3):
      tot += (int(img1[p-1][i][c]) - int(img2[0][i][c]))**2
  return tot

구현은 아주 단순합니다. 두 이미지의 경계의 픽셀들에 대해 RGB값의 차이의 제곱을 모두 합한 결과가 작으면 작을수록 실제로 인접한 조각이라고 판단하겠다는 의미입니다. 즉 반환한 점수가 작으면 작을수록 실제로 인접한 조각일 가능성이 클 것입니다.

저희가 확인해봐야할 것은, 이렇게 찾아낸 인접한 조각이 실제로 인접한 조각과 얼마나 일치하냐는 문제였습니다. 이를 확인하기 위해 정상적인 고양이 그림을 8x8, 16x16, 32x32 크기로 쪼개서 위와 같은 방식으로 점수를 계산했을 때 실제 인접한 조각이 전체 조각 중에서 점수가 작은 순으로 몇 번째인지를 확인해보았습니다. 이상적인 상황에서는 모두 1번째이어야 할 것입니다. 아래의 코드가 이를 확인하는 코드입니다.

def test2():
  for p in [16, 32, 64]:
    m = 512 // p
    f = open('shuffled-images-data/data_train/data_train_{}_answers.txt'.format(p))
    rank = [0]*21
    for _ in range(600):
      name = f.readline().strip()
      print("file "+name)
      ans = list(map(int,f.readline().split()))
      img = cv2.imread('shuffled-images-data/data_train/{}/'.format(p)+name)
      L = slice_photo(img, p)
      #print(score2_col(L[0],L[1],p))
      #exit()
      cost_row = [[0]*(m*m) for i in range(m*m)]
      cost_col = [[0]*(m*m) for i in range(m*m)]
      for i in range(m*m): cost_row[i][i] = cost_col[i][i] = 10**10
      for i in range(m*m):
        for j in range(m*m):
          if i==j: continue
          v1 = score1_row(L[i],L[j],p)
          v2 = score1_col(L[i],L[j],p)          
          cost_row[i][j] = v1
          cost_col[i][j] = v2
          print(v1, score2_row(L[i],L[j],p))
          print(v2, score2_col(L[i],L[j],p))
          
      
      for i in range(m*m):
        mn = min(cost_row[i])
        if mn == 0: mn = 0.01
        for j in range(m*m): cost_row[i][j] /= mn
      
      for i in range(m*m):
        mn = min(cost_col[i])
        if mn == 0: mn = 0.01
        for j in range(m*m): cost_col[i][j] /= mn

      for i in range(m*m):
        if i%m == 0: continue
        if i>=m*m-m: continue
        idx1 = ans[i]
        idx2 = ans[i+m-1]
        tmp = []
        for j in range(m*m):
          if j == idx1 or j == idx2: continue
          tmp.append(cost_col[idx1][j]+cost_row[idx2][j])
        tmp.sort()
        val = cost_col[idx1][ans[i+m]]+cost_row[idx2][ans[i+m]]
        idx = tmp.index(val)
        rank[min(20,idx)] += 1
        if idx != 0: print(idx, val, tmp[0])

     
      print(rank)

확인 결과는 아래와 같습니다(20위 밖의 것은 전부 20위로 몰아서 생각했습니다).

8x8
[5414, 22, 8, 9, 9, 7, 3, 3, 1, 2, 1, 3, 3, 0, 0, 0, 0, 2, 0, 0, 1]

16x16
[8695, 127, 30, 32, 22, 10, 12, 8, 5, 6, 5, 6, 2, 3, 5, 1, 4, 4, 0, 1, 22]

32x32
[7502, 299, 142, 101, 55, 33, 49, 29, 31, 20, 19, 18, 18, 17, 8, 8, 8, 8, 10, 13, 261]

8x8에서는 1.35%, 16x16에서는 3.39%, 32x32에서는 13.3% 정도의 조각에 대해 순위가 잘못 매겨졌음을 알 수 있습니다.

RGB로 단순 비교하는 것은 분명 괜찮은 접근법이지만 여러 조각으로 나누어져있을 때에는 많이 부정확합니다.

인접한 조각 찾기 - MGC(Mahalanobis Gradient Compatibility)

인접한 조각을 찾기 위한 또 다른 점수로는 MGC(Mahalanobis Gradient Compatibility)가 있습니다. 이 방식은 Jigsaw Puzzle with Pieces of Unknown Orientation이라는 논문에서 처음 제안된 방식입니다.

RGB로 단순하게 점수를 계산하는 방식은 첫 번째로 경계 주변에서 색깔이 변화하고 있을 때 이 부분이 반영되지 못한다는 문제가 있고, 두 번째로 같은 인접한 쌍임에도 불구하고 색깔 변화가 작은 쌍과 큰 쌍의 점수 차이가 많이 커서 추후에 전체 그림에 대한 완성도를 계산할 때 문제가 될 수 있다는 문제가 있습니다.

이를 개선하기 위해 왼쪽 조각의 오른쪽 두 행에서의 색깔 값을 가지고 Mahalanobis distance를 구하는 방식이 논문에서 소개하는 MGC입니다. MGC는 값에 색의 변화가 드러나고 또 평균과의 거리가 표준편차의 몇 배인지를 나타내는 것이 Mahalanobis distance 이기 때문에 절대적인 색깔 값의 차이와 무관하게 점수가 계산된다는 장점이 있습니다. 이를 구현한 코드는 아래와 같습니다.

# MGC
# Jigsaw Puzzles with Pieces of Unknown Orientation - Andrew C. Gallagher
def score2_row(img1, img2, p):
  g1 = img1[:, -1] - img1[:, -2]  
  mu = g1.mean(axis = 0)
  s = np.cov(g1.T) + np.eye(3) * (10**-5)
  g2 = img2[:, 0] - img1[:, -1]
  sinv = np.linalg.inv(s)
  val1 = sum(mahalanobis(x, mu, sinv) for x in g2)

  g3 = img2[:, 1] - img2[:, 0]
  mu = g3.mean(axis = 0)
  s = np.cov(g3.T) + np.eye(3) * (10**-5)
  g4 = img2[:, 0] - img1[:, -1]
  sinv = np.linalg.inv(s)
  val2 = sum(mahalanobis(x, mu, sinv) for x in g2)
  return val1+val2

def score2_col(img1, img2, p):
  g1 = img1[-1, :] - img1[-2, :]
  mu = g1.mean(axis = 0)
  s = np.cov(g1.T) + np.eye(3) * (10**-5)
  g2 = img2[0, :] - img1[-1, :]
  sinv = np.linalg.inv(s)
  val1 = sum(mahalanobis(x, mu, sinv) for x in g2)

  g3 = img2[1, :] - img2[0, :]
  mu = g3.mean(axis = 0)
  s = np.cov(g3.T) + np.eye(3) * (10**-5)
  g4 = img2[0,:] - img1[-1, :]
  sinv = np.linalg.inv(s)
  val2 = sum(mahalanobis(x, mu, sinv) for x in g2)
  return val1+val2

MGC로 계산한 점수에 대해서도 마찬가지로 순위가 잘 나오는지를 확인해보았습니다. 결과는 아래와 같습니다.

8x8
[4210, 27, 1, 2, 3, 0, 0, 4, 2, 0, 2, 0, 2, 1, 0, 0, 0, 0, 1, 0, 1]
16x16
[1887, 18, 7, 4, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
32x32
[1879, 38, 14, 6, 7, 2, 3, 3, 2, 1, 1, 1, 3, 2, 0, 1, 0, 1, 0, 0, 20]

8x8에서는 1.08%, 16x16에서는 1.72%, 32x32에서는 5.29% 정도의 조각에 대해 순위가 잘못 매겨졌음을 알 수 있습니다.

각 조각의 가로세로가 16픽셀밖에 안되는 32x32에서는 여전히 오류가 꽤 있는 편이지만 RGB에 비해서는 개선이 많이 되었음을 알 수 있습니다. 이제 이 정보를 이용해 실제로 어떻게 퍼즐을 맞출지 고민해봅시다.

방법 1 - Hungarian Method

모든 조각을 복사해 두 그룹으로 나눈 뒤 이분그래프 모양으로 만듭니다. 그리고 간선의 값이 좌우의 점수라고 그래프를 모델링을 하고 나면 이분그래프에서의 매칭 문제로 환원할 수 있고 이 문제는 Hungarian Method로 해결이 가능합니다. 이후 상하에 대한 점수도 모델링을 하면 각 조각에 대해 오른쪽과 아랫쪽에 와야 하는 조각이 무엇인지를 알 수 있습니다.

단, 이 때 오른쪽 변에 있는 조각이나 아랫쪽 변에 있는 조각은 각각 오른쪽, 아랫쪽에 인접한 조각이 없으므로 8x8 기준 실제 모델링을 할 때에는 8개의 dummy node를 왼쪽, 오른쪽에 배치했습니다.

당연하게도 이 모델링이 항상 올바른 답을 주지는 않습니다. 예를 들어서 단 한개의 조각만 오른쪽과 아랫쪽의 조각이 없어야 하지만 Hungarian의 최적해를 구했더니 이러한 조각이 여러 개일 수도 있고, 없을 수도 있습니다. 그러니 올바른 답이 구해지는 경우에 한해서만 답을 만들게 했습니다.

#cost : 1-indexed
INF = 0x3f3f3f3f3f3f3f
def Hungarian(cost, n):
  p = [0] * (n+1)
  u = [0] * (n+1)
  v = [0] * (n+1)
  minv = [INF] * (n+1)
  way = [0] * (n+1)
  used = [0] * (n+1)
  match = [0] * (n+1)
  for i in range(1, n+1):
    p[0] = i
    b = 0
    minv = [INF] * (n+1)
    used = [0] * (n+1)
    while True:
      used[b] = 1
      a = p[b]
      delta = INF
      j1 = 0
      for j in range(1,n+1):
        if used[j]: continue
        cur = cost[a][j] - u[a] - v[j]
        if cur < minv[j]:
          minv[j] = cur
          way[j] = b
        if minv[j] < delta:
          delta = minv[j]
          j1 = j
      
      for j in range(0,n+1):
        if used[j]:
          u[p[j]] += delta
          v[j] -= delta
        else:
          minv[j] -= delta
      
      b = j1
      if p[b] == 0: break
    
    while True:
      j1 = way[b]
      p[b] = p[j1]
      b = j1
      if b == 0: break

  for j in range(1,n+1):
    match[p[j]] = j
  return match, -v[0]

# p*p images, using hungarian method
def solve_hungarian(img, p, filename):
  m = 512 // p
  L = slice_photo(img, p)
  cost_row = [[0] * (m*m+m+1) for i in range(m*m+m+1)]
  cost_col = [[0] * (m*m+m+1) for i in range(m*m+m+1)]
  for i in range(m*m,m*m+m):
    for j in range(m*m,m*m+m):
      cost_row[i+1][j+1] = cost_col[i+1][j+1] = INF
  for i in range(m*m):
    for j in range(m*m):
      if i == j:
        cost_row[i+1][j+1] = INF
        cost_col[i+1][j+1] = INF
        continue
      cost_row[i+1][j+1] = score1_row(L[i], L[j], p)
      cost_col[i+1][j+1] = score1_col(L[i], L[j], p)
  
  match_LR = Hungarian(cost_row, m*m+m)[0][1:]
  match_UD = Hungarian(cost_col, m*m+m)[0][1:]

  # 0-indexed
  match_LR = [x-1 for x in match_LR] # L->R
  match_UD = [x-1 for x in match_UD] # U->D

  match_RL = [0]*(m*m+m) # R->L
  match_DU = [0]*(m*m+m) # D->U
  
  for i in range(m*m+m):
    match_RL[match_LR[i]] = i
    match_DU[match_UD[i]] = i
  
  cnt = 0

  ul = ur = dl = dr = -1
#  print('up-left')
  for i in range(m*m):
    if match_RL[i] >= m*m and match_DU[i] >= m*m:
      if ul != -1:
        return -1
      ul = i

  
#  print('up-right')
  for i in range(m*m):
    if match_LR[i] >= m*m and match_DU[i] >= m*m:
      if ur != -1:
        return -1
      ur = i
  
#  print('down-left')
  for i in range(m*m):
    if match_RL[i] >= m*m and match_UD[i] >= m*m:
      if dl != -1:
        return -1
      dl = i
  
#  print('down-right')
  for i in range(m*m):
    if match_LR[i] >= m*m and match_UD[i] >= m*m:
      if dr != -1:
        return -1
      dr = i

  if -1 in [ul,ur,dl,dr]: return -1
  result = np.ndarray(shape=(512,512,3), dtype=np.uint8)
  ans = [[0]*m for i in range(m)]
  ans[0][0] = ul
  for i in range(1,m):
    ans[0][i] = match_LR[ans[0][i-1]]
    ans[i][0] = match_UD[ans[i-1][0]]
  
  for i in range(1,m):
    for j in range(1,m):
      ans[i][j] = match_LR[ans[i][j-1]]
      if match_UD[ans[i-1][j]] != ans[i][j]:
        return -1
  
  for i in range(0,m):
    for j in range(0,m):
      result[p*i:p*i+p, p*j:p*j+p, 0:3] = L[ans[i][j]//m][ans[i][j]%m]

  #cv2.imshow('result', result)
  #cv2.waitKey(0)
  #cv2.destroyAllWindows()
  return 1

아쉽게도 8x8 기준으로 그림 10개당 1개 꼴로만 그림 복원에 성공했고 대부분의 그림에서는 복원이 잘 이루어지지 않았습니다. 16x16, 32x32에서는 전혀 복원에 성공하지 못했습니다.

방법 2 - 작은 정사각형부터 만들기

이 방법은 (Solving Square Jigsaw Puzzles with Loop Constraints)[https://link.springer.com/chapter/10.1007/978-3-319-10599-4_3] 논문을 읽다가 갑자기 아이디어가 생겨서 적용해본 방법입니다.

제가 생각한 방법은 임의의 조각을 왼쪽 상단으로 정해두고 오른쪽과 아랫쪽 한 줄을 게속 늘려가는 방식으로 1x1, 2x2, 이렇게 그림을 확장해나가다 8x8 전체 그림을 만드는 방법입니다.

예를 들어 4x4에서 5x5를 만들 때 (5, 1)과 (1, 5)만 정하고 나면 나머지 빈 조각들은 주변에 반드시 2개의 이미 정해진 조각이 있습니다. 아직 쓰지 않은 조각 중에서 임의로 2개를 뽑아 (5, 1)과 (1, 5)에 놓아보고 나머지 조각들은 그러므로 인접한 2개와의 점수의 합이 작은 것을 택하도록 하도록 했습니다. 이렇게 해서 전체적으로 점수가 가장 낮은 것을 택하도록 했습니다.

Python으로 구현하니 너무 느려서 Python에서는 점수를 텍스트파일로 저장하고 C++에서 해당 점수를 읽어와 연산을 수행하도록 했습니다. 다소 코드가 길고 단순 구현 느낌이 강해 코드에서 크게 확인할 것은 없지만 그래도 재현해보고 싶은 분을 위해 코드를 첨부합니다.

#include <bits/stdc++.h>

using namespace std;


typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

bool OOB(ll x, ll y, ll N, ll M) { return 0 > x || x >= N || 0 > y || y >= M; }

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()


int board[1024][32][32];
int board_score[1024];
int score_col[1024][1024];
int score_row[1024][1024];
vector<bool> used[1024];
bool WRITE = 1;

int test(){
  int ans[8][8]={
  {0, 1, 25, 52, 31, 16, 13, 40, },{36, 58, 21, 22, 28, 27, 51, 59, },{18, 37, 10, 34, 44, 14, 2, 49, },
  {63, 35, 30, 55, 42, 54, 57, 62, },{19, 48, 4, 50, 23, 46, 26, 38, },{7, 53, 20, 29, 60, 3, 12, 8, },
  {39, 41, 47, 56, 15, 17, 24, 61, },{ 6, 33, 9, 11, 45, 32, 5, 43, }
  };

  rep(step,1,8){
    int val = 0;
    rep(i,0,step+1){
      rep(j,0,step+1){
        if(i != step) val += score_col[ans[i][j]][ans[i+1][j]];
        if(j != step) val += score_row[ans[i][j]][ans[i][j+1]];        
      }
    }
  }
}
int main(){

  int p = 64;
  int m = 512 / p;
  rep(i,0,m*m) used[i].resize(m*m);
  
  for(int f = 2400; f < 2700; f++){
    FILE* result;
    if(WRITE) result = fopen("result/A2.txt","a");
    string ff = to_string(f);
    while(ff.size() < 4) ff = "0"+ff;
    if(WRITE) fprintf(result, "%s.png\n", ff.c_str());
    string path = "C:/Users/win10/Documents/dat/score_data/data_test1_blank/"+to_string(p)+"/"+ff+".txt";
    cout << path << '\n';
    FILE* fp = fopen(path.c_str(),"r");
    assert(fp != NULL);
    rep(i,0,m*m)rep(j,0,m*m) fscanf(fp, "%d", &score_row[i][j]);
    rep(i,0,m*m)rep(j,0,m*m) fscanf(fp, "%d", &score_col[i][j]);       
    fclose(fp);
    memset(board, 0, sizeof(board));
    fill(board_score, board_score+1024, 0);
    //test();
    rep(i,0,m*m) fill(all(used[i]),false);
    rep(i,0,m*m){
      board[i][0][0] = i;
      used[i][i] = true;
    }
    rep(step,1,m){
      rep(st,0,m*m){
        vector<int> unused;
        rep(i,0,m*m){
          if(!used[st][i]) unused.pb(i);         
        }        
        int min_score = 0x7f7f7f7f;
        int best_ru = -1, best_ld = -1;
        for(auto ru : unused){
          board[st][0][step] = ru;
          int cur_score1 = score_row[board[st][0][step-1]][ru];
          vector<int> tmp;
          tmp.pb(ru);
          // (i, step)
          for(int i = 1; i < step; i++){
            int mn = 0x7f7f7f7f;
            for(auto x : unused){
              if(find(all(tmp), x) != tmp.end()) continue;
              int tmp_score = score_row[ board[st][i][step-1] ][x] + score_col[ board[st][i-1][step] ][x];
              if(tmp_score < mn){
                mn = tmp_score;
                board[st][i][step] = x;
              }
            }
            cur_score1 += mn;
            tmp.pb(board[st][i][step]);            
          }
          for(auto ld : unused){
            if(find(all(tmp),ld) != tmp.end()) continue;
            tmp.pb(ld);
            board[st][step][0] = ld;
            int cur_score2 = score_col[ board[st][step-1][0] ][ld];            
            // (step, i)
            for(int i = 1; i < step; i++){
              int mn = 0x7f7f7f7f;
              for(auto x : unused){
                if(find(all(tmp), x) != tmp.end()) continue;
                int tmp_score = score_row[ board[st][step][i-1] ][x] + score_col[ board[st][step-1][i] ][x];
                if(tmp_score < mn){
                  mn = tmp_score;
                  board[st][step][i] = x;
                }
              }
              cur_score2 += mn;
              tmp.pb(board[st][step][i]);      
            }

            // (step, step)
            int mn = 0x7f7f7f7f;
            for(auto x : unused){
              if(find(all(tmp),x) != tmp.end()) continue;
              int tmp_score = score_row[ board[st][step][step-1] ][x] + score_col[ board[st][step-1][step] ][x];
              if(tmp_score < mn){
                mn = tmp_score;
                board[st][step][step] = x;
              }
            }
            
            if(min_score > cur_score1 + cur_score2 + mn){
              min_score = cur_score1 + cur_score2 + mn;
              best_ru = ru;
              best_ld = ld;
            }
            rep(i,0,step) tmp.pop_back();
          }
        }
        board_score[st] += min_score;        
        board[st][0][step] = best_ru;
        board[st][step][0] = best_ld;
        used[st][best_ru] = true;
        used[st][best_ld] = true;
        for(int i = 1; i < step; i++){
          int mn = 0x7f7f7f7f;
          rep(x,0,m*m){
            if(used[st][x]) continue;
            int tmp_score = score_row[ board[st][i][step-1] ][x] + score_col[ board[st][i-1][step] ][x];
            if(tmp_score < mn){
              mn = tmp_score;
              board[st][i][step] = x;
            }
          }
          used[st][board[st][i][step]] = true;          
        }

        for(int i = 1; i < step; i++){
          int mn = 0x7f7f7f7f;
          rep(x,0,m*m){
            if(used[st][x]) continue;
            int tmp_score = score_row[ board[st][step][i-1] ][x] + score_col[ board[st][step-1][i] ][x];
            if(tmp_score < mn){
              mn = tmp_score;
              board[st][step][i] = x;
            }
          }
          used[st][board[st][step][i]] = true;  
        }

        int mn = 0x7f7f7f7f;
        rep(x,0,m*m){
          if(used[st][x]) continue;
          int tmp_score = score_row[ board[st][step][step-1] ][x] + score_col[ board[st][step-1][step] ][x];
          if(tmp_score < mn){
            mn = tmp_score;
            board[st][step][step] = x;
          }
        }
        used[st][board[st][step][step]] = true;  
      }      
    }
    int min_idx = min_element(board_score, board_score+(m*m)) - board_score;

    rep(i,0,m){
      rep(j,0,m){
        printf("%d ", board[min_idx][i][j]);
        if(WRITE) fprintf(result, "%d", board[min_idx][i][j]);
        if(WRITE)
        {
          if(i!=m-1 or j!=m-1) fprintf(result, " ");
          else fprintf(result, "\n");
        }
      }      
    }
    printf("\n");
    if(WRITE) fclose(result);    
  }  
}

구현 결과는 아래와 같이 그럭저럭 준수했습니다.

구현 결과

고양이 사진이 꽤 잘 복구되었음을 알 수 있습니다. 실제로 제출했을 때 대략 97% 정도의 쌍이 정확하게 매칭되었습니다. 점수로 환산했을 때 30000점 만점에 대략 29200점 정도였습니다. 다만 육안으로 보았을 때 문제가 있는 그림들도 아래와 같이 쉽게 찾을 수 있었습니다.

깨진 그림 1

깨진 그림 2

이 방식의 가장 큰 문제는, 시간이 너무나도 오래 걸린다는 점이었습니다. 8x8은 각 그림당 10초 내외로 결과를 얻을 수 있었지만 16x16은 거의 10분 가까이 필요했고 32x32는 현실적인 시간 내로 답이 나올 것 같지 않아보였습니다. 그림이 각 크기들에 대해 300개씩 존재했기 때문에 획기적인 개선이 필요했습니다.

여러 가지 방식으로 최적화를 해서 개선을 할 수 있었겠지만 ICPC의 압박으로 인해(ㅠㅠ) 여기서 도전을 멈춰야했습니다.

개선할 점과 후기

만약 제가 이 문제에 더 적극적으로 도전할 수 있었다면 우선 작은 정사각형부터 만드는 방식을 개선해 답을 찾고, 다른 논문에서 제안되었던 Minimum Spanning Tree, Linear Programming 등을 익힐 생각을 했을 것입니다. 그렇게 하더라도 1등까지 할 자신은 없지만 그래도 상위권에는 들 수 있었을 것 같습니다.

이런 휴리스틱 문제를 풀어본 것이 육목 대회 이후 두 번째였습니다.

그 때나 지금이나 일단 관련된 논문을 찾고 1mm씩 조금씩과 같은 느낌으로 어떻게든 프로토타입을 만든 후 개선해나간다는 큰 틀은 바뀌지 않았습니다. 다소 난해했고 좋은 결과를 내지는 못했지만 그래도 재밌는 도전이었습니다. 다음에 또 비슷한 챌린지가 있다면 도전해봐야겠습니다!