문제

• https://www.acmicpc.net/problem/14620

대충 요약하면 각 element가 일정 수치를 갖는 정방형 배열이 주어지고 ,이 배열에 십자 모양(5칸)으로 겹치지 않게 3번 색칠할 때, 색칠된 영역의 수치 합의 최소값을 구하라는 것이다.

풀이

DFS로 풀이하였다.

C++17

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int cost[10][10] = {0};
bool visit[10][10] = {false};
int n=0;
int mini = 10000;
int di[4] = {0, 0, 1 ,-1};
int dj[4] = {1,-1,0,0};

bool whole_check(int i0, int j0) {
  if(visit[i0][j0]) {
    return false;
  }
  for(int idx=0; idx<4;idx++) {
    int i1 = i0+di[idx];
    int j1 = j0+dj[idx];
    if(i1<0 || i1>n-1 || j1<0 || j1>n-1|| visit[i1][j1]) {
      return false;
    }
  }
  return true;
}

void dfs(int count, int sum, int start_i) {
  if(count==3) {
    if(mini > sum) {
      mini = sum;
    }
    return;
  }

  for(int i=start_i; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(!whole_check(i, j)) {
        continue;
      }

      int s = cost[i][j];
      visit[i][j] = true;
      for(int idx=0; idx<4;idx++) {
        int i1 = i+di[idx];
        int j1 = j+dj[idx];
        visit[i1][j1] = true;
        s += cost[i1][j1];
      }

      dfs(count+1, sum+s, i);

      visit[i][j] = false;      
      for(int idx=0; idx<4;idx++) {
        int i1 = i+di[idx];
        int j1 = j+dj[idx];
        visit[i1][j1] = false;
      }
    }
  }
}

int main() {
  scanf("%d", &n);
  for(int i=0;i<n;i++) {
    for(int j=0; j<n;j++) {
      scanf("%d", &(cost[i][j]));
    }
  }
  dfs(0,0,1);
  cout << mini;
}

Python3

n=int(input()); m=[list(map(int, input().split())) for i in range(n)]
visit_m = [[True for j in range(n)] for i in range(n)]
pay_func = lambda i,j:m[i-1][j] + m[i+1][j] + m[i][j+1] + m[i][j-1] + m[i][j]
di = [0,0,1,-1]
dj = [1,-1,0,0]
minimum = 10000

def check_func(i0,j0):
	global visit_m
	if not visit_m[i0][j0]: 
		return False
	for c in range(4):
		i= i0+di[c]
		j= j0+dj[c]
		if not ((0<=i and i<n and 0<=j and j<n) and visit_m[i][j]):
			return False
	return True

def solve(c, sum0):
	global minimum, visit_m
	if c == 3:
		if sum0 < minimum: 
			minimum = sum0
		return
	for i in range(n):
		for j in range(n):
			if not check_func(i,j): 
				continue
			visit_m[i][j] = False
			s = m[i][j]
			for idx in range(4):
				visit_m[i+di[idx]][j+dj[idx]] = False
				s += m[i+di[idx]][j+dj[idx]]
			solve(c+1, sum0+s)

			visit_m[i][j] = True
			for idx in range(4):
				visit_m[i+di[idx]][j+dj[idx]] = True
			s=0

solve(0,0)
print(minimum)

별생각없이 풀었다가 상당히 피를 봤다. 헷갈리기 쉬운 변수명을 사용했다가 1시간동안 "왜맞틀?!"을 시전했다. 이것 외에도 문제를 풀면서 얻은 교훈들이 있는데 이는 이후 목차에 기술하겠다.

발생할 비용의 모든 경우의 수를 구한 후 최솟값을 얻으면 되겠다라고 생각했다. 이를 위해 DFS를 사용하여 모든 경우의 수를 탐색하였다.

이 자리에 씨앗을 심어 꽃을 피울 수 있는 지 먼저 확인한 후, 심을 수 있다면 꽃의 위치를 표시했다. 그 다음으로 재귀 형태로 탐색함수를 호출하였다. 파라미터로 현재 "비용 합"+"방금 심은 꽃을 위한 비용", 몇개 째 심은 것인지 넘겨주었다. 재귀함수가 리턴되면 방금 심은 꽃의 위치를 지웠다.

씨앗이 심어지는 위치와 피어나 꽃잎이 차지하는 위치에는 다른 씨앗이나 꽃잎이 접근하지 못하도록 visit 표시를 해주었다.

꽃은 십자형으로 피어나기 때문에 씨앗을 1행부터 심을 수 있다. 시간을 조금 줄이기 위해 1행부터 탐색을 시작하도록 하였다.

파이썬으로 풀고 C++로도 풀었다.
처음 파이썬으로 풀었을 때 자꾸 틀려서 시간초과인줄 알고 C++로 다시 풀었다. 몇 번을 삽질한 끝에 무엇이 잘못되었는지 깨달았다. 비용 최대합은 600이 아니구나...... 문제를 대충 본 내 잘못이다.

느낀점

1. 변수명은 i, j는 귀찮아도 쓰지 말자.
2. 최소값을 타나내는 변수의 초기 값은 그냥 자료형의 최대 값으로 하자.