문제 링크 : https://www.acmicpc.net/contest/view/505

--------------- 스포방지 ---------------

I. 스티커 붙이기

C++

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

int n, m, k;
int note[42][42];
int r, c;
int paper[12][12];

// paper를 90도 회전하는 함수
void rotate(){
  int tmp[12][12];
  
  for(int i = 0; i < r; i++)
    for(int j = 0; j < c; j++)
      tmp[i][j] = paper[i][j];
  
  for(int i = 0; i < c; i++)
    for(int j = 0; j < r; j++)
      paper[i][j] = tmp[r-1-j][i];

  swap(r, c);
}


// note의 (x,y)에 모눈종이의 (0,0)이 올라가게 스티커를 붙일 수 있는지 판단하는 함수. 가능할 경우 note를 갱신한 후 true를 반환.
bool pastable(int x, int y){
  for(int i = 0; i < r; i++){
    for(int j = 0; j < c; j++){
      if(note[x+i][y+j] == 1 && paper[i][j] == 1)
        return false;
    }
  }
  for(int i = 0; i < r; i++){
    for(int j = 0; j < c; j++){
      if(paper[i][j] == 1)
        note[x+i][y+j] = 1;
    }
  }
  return true;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  while(k--){
    cin >> r >> c;
    for(int i = 0; i < r; i++)
      for(int j = 0; j < c; j++)
        cin >> paper[i][j];
    
    for(int rot = 0; rot < 4; rot++){
      bool is_paste = false; // 해당 스티커를 붙였는가?
      for(int x = 0; x <= n-r; x++){
        if(is_paste) break;
        for(int y = 0; y <= m-c; y++){
          if(pastable(x, y)){
            is_paste = true;
            break;
          }
        }
      }
      if(is_paste) break;
      rotate();
    }
  }
  int cnt = 0;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      cnt += note[i][j];
  cout << cnt << '\n';
}

JAVA

import java.util.*;
import java.io.*;
import java.lang.*;
public class Main{
  static int n, m, k;
  static int[][] note;
  static int r, c;
  static int[][] paper;
  static void rotate(){
    int[][] tmp = new int[r][c];
    for(int i = 0; i < r; i++)
      for(int j = 0; j < c; j++)
        tmp[i][j] = paper[i][j];

    for(int i = 0; i < c; i++)
      for(int j = 0; j < r; j++)
        paper[i][j] = tmp[r-1-j][i];

    int t = r;
    r = c;
    c = t;
  }

  static boolean pasteable(int x, int y){
    for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
        if(note[x+i][y+j] == 1 && paper[i][j] == 1)
          return false;
      }
    }
    for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
        if(paper[i][j] == 1)
          note[x+i][y+j] = 1;
      }
    }
    return true;
  }
  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    note = new int[n][m];

    for(int zz = 0; zz < k; zz++){ // k번 반복
      st = new StringTokenizer(br.readLine(), " ");
      r = Integer.parseInt(st.nextToken());
      c = Integer.parseInt(st.nextToken());
      paper = new int[Math.max(r,c)][Math.max(r,c)];
      for(int i = 0; i < r; i++){
        st = new StringTokenizer(br.readLine(), " ");
        for(int j = 0; j < c; j++)
          paper[i][j] = Integer.parseInt(st.nextToken());
      }
      for(int rot = 0; rot < 4; rot++){
        boolean is_paste = false;
        for(int x = 0; x <= n-r; x++){
          if(is_paste) break;
          for(int y = 0; y <= m-c; y++){
            if(pasteable(x,y)){
              is_paste = true;
              break;
            }
          }
        }
        if(is_paste) break;
        if(rot != 3) rotate();
      }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        cnt += note[i][j];
    bw.write(Integer.toString(cnt) + "\n");
    br.close();
    bw.close();
  }
}

Python

import sys
input = sys.stdin.readline

n,m,k = map(int, input().split())
note = [[0]*m for i in range(n)]

def rotate(paper):
  r, c = len(paper), len(paper[0])
  return [[paper[r-1-j][i] for j in range(r)] for i in range(c)]
'''
  tmp = [[0]*r for i in range(c)]
  for i in range(c):
    for j in range(r):
      tmp[i][j] = paper[r-1-j][i]
  return tmp
'''
def pastable(x, y):
  if any(note[x+i][y+j] == 1 and paper[i][j] == 1 for i in range(r) for j in range(c)):
    return False
  for i in range(r):
    for j in range(c):
      if paper[i][j] == 1:
        note[x+i][y+j] = 1  
  return True

'''
def pastable(x, y):

  for i in range(r):
    for j in range(c):
      if(note[x+i][y+j] == 1 and paper[i][j] == 1):
        return False


  for i in range(r):
    for j in range(c):
      if paper[i][j] == 1:
        note[x+i][y+j] = 1

  return True
'''
for _ in range(k):
  r, c = map(int, input().split())
  paper = [list(map(int, input().split())) for _ in range(r)]
  for rot in range(4):
    is_paste = False
    for x in range(n-r+1):
      if is_paste: break
      for y in range(m-c+1):
        if pastable(x,y):
          is_paste = True
          break
    if is_paste: break
    if rot != 3:
      paper = rotate(paper)
      r, c = c, r

sys.stdout.write(str(sum([sum(L) for L in note])))

II. Gaaaaaaaaaarden

C++ (next_permutation)

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,g,r;
int board[52][52];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int> > cand;
int candsz;
const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;
// next_permutaion을 위한 변수, cand가 7이고 g=1,r=4일 때 {0,0,1,2,2,2,2}
int brute[10];
int solve(){
  int cnt = 0;
  pair<int,int> state[52][52]; // {arrival time, color}

  queue<pair<int,int>> q;
  for(int i = 0; i < candsz; i++){
    if(brute[i] == GREEN || brute[i] == RED){
      state[cand[i].X][cand[i].Y] = {0, brute[i]};
      q.push(cand[i]);
    }
  }
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    int curtime = state[cur.X][cur.Y].X;
    int curcolor = state[cur.X][cur.Y].Y;
    if(state[cur.X][cur.Y].Y == FLOWER) continue;
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(board[nx][ny] == 0) continue;
      if(state[nx][ny].Y == EMPTY){
        state[nx][ny] = {curtime+1, curcolor};
        q.push({nx,ny});
      }
      else if(state[nx][ny].Y == RED){
        if(curcolor == GREEN && state[nx][ny].X == curtime+1){
          cnt++;
          state[nx][ny].Y = FLOWER;
        }
      }
      else if(state[nx][ny].Y == GREEN){
        if(curcolor == RED && state[nx][ny].X == curtime+1){
          cnt++;
          state[nx][ny].Y = FLOWER;
        }        
      }
    }
  }
  return cnt;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> g >> r;  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      assert(board[i][j] >= 0 && board[i][j] <= 2);
      if(board[i][j] == 2)
        cand.push_back({i,j});
    }
  }
  candsz = cand.size();
  fill(brute+candsz-g-r, brute+candsz-r,GREEN);
  fill(brute+candsz-r, brute+candsz,RED);
  int mx = 0;
  do{
    mx = max(mx, solve());
  }while(next_permutation(brute, brute+candsz));
  cout << mx << '\n';
}

C++ (백트래킹)

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,g,r;
int board[52][52];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int> > cand;
int candsz;
const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;
// backtracking을 위한 변수
bool isused[10];
// 초록/빨강 배양액으로 선택한 위치의 index
int chosen_g[5], chosen_r[5]; 

int mx;


int solve(){
  int cnt = 0;
  pair<int,int> state[52][52]; // {arrival time, color}

  queue<pair<int,int>> q;
  for(int i = 0; i < g; i++){
    state[cand[chosen_g[i]].X][cand[chosen_g[i]].Y] = {0, GREEN};
    q.push(cand[chosen_g[i]]);
  }
  for(int i = 0; i < r; i++){
    state[cand[chosen_r[i]].X][cand[chosen_r[i]].Y] = {0, RED};
    q.push(cand[chosen_r[i]]);
  }

  while(!q.empty()){
    auto cur = q.front(); q.pop();
    int curtime = state[cur.X][cur.Y].X;
    int curcolor = state[cur.X][cur.Y].Y;
    if(state[cur.X][cur.Y].Y == FLOWER) continue;
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(board[nx][ny] == 0) continue;
      if(state[nx][ny].Y == EMPTY){
        state[nx][ny] = {curtime+1, curcolor};
        q.push({nx,ny});
      }
      else if(state[nx][ny].Y == RED){
        if(curcolor == GREEN && state[nx][ny].X == curtime+1){
          cnt++;
          state[nx][ny].Y = FLOWER;
        }
      }
      else if(state[nx][ny].Y == GREEN){
        if(curcolor == RED && state[nx][ny].X == curtime+1){
          cnt++;
          state[nx][ny].Y = FLOWER;
        }        
      }
    }
  }
  return cnt;
}

void select_r(int idx){
  if(idx == r){
    mx = max(mx, solve());
    return;
  }
  int cur = 0;
  if(idx != 0) cur = chosen_r[idx-1]+1;
  while(cur < candsz){
    if(isused[cur]){
      cur++;
      continue;
    }
    isused[cur] = true;
    chosen_r[idx] = cur;
    select_r(idx+1);
    isused[cur] = false;
    cur++;
  }
}
void select_g(int idx){
  if(idx == g){
    select_r(0);
    return;
  }
  int cur = 0;
  if(idx != 0) cur = chosen_g[idx-1]+1;
  while(cur < candsz){
    isused[cur] = true;
    chosen_g[idx] = cur;
    select_g(idx+1);
    isused[cur] = false;
    cur++;
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> g >> r;  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 2)
        cand.push_back({i,j});
    }
  }
  candsz = cand.size();
  select_g(0);
  cout << mx << '\n';
}

JAVA

import java.util.*;
import java.io.*;
public class Main{
  static int n, m, g, r;
  static int[][] board;
  static int dx[] = {1,0,-1,0};
  static int dy[] = {0,1,0,-1};
  static int mx = 0;
  static int[] candx = new int[10];
  static int[] candy = new int[10];
  static int candsz = 0;
  static final int EMPTY = 0;
  static final int GREEN = 1;
  static final int RED = 2;
  static final int FLOWER = 3;
  static boolean[] isused = new boolean[10];
  static int[] chosen_g = new int[5];
  static int[] chosen_r = new int[5];  
  static int solve(){
    int cnt = 0;
    Pair[][] state = new Pair[n][m]; // {arival time, color}
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        state[i][j] = new Pair();
    Queue<Pair> q = new LinkedList<>();
    for(int i = 0; i < g; i++){
      state[candx[chosen_g[i]]][candy[chosen_g[i]]] = new Pair(0, GREEN);
      q.add(new Pair(candx[chosen_g[i]],candy[chosen_g[i]]));
    }
    for(int i = 0; i < r; i++){
      state[candx[chosen_r[i]]][candy[chosen_r[i]]] = new Pair(0, RED);
      q.add(new Pair(candx[chosen_r[i]],candy[chosen_r[i]]));
    }
    while(!q.isEmpty()){
      Pair cur = q.poll();
      int curtime = state[cur.x][cur.y].x;
      int curcolor = state[cur.x][cur.y].y;
      if(state[cur.x][cur.y].y == FLOWER) continue;
      for(int dir = 0; dir < 4; dir++){
        int nx = cur.x + dx[dir];
        int ny = cur.y + dy[dir];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if(board[nx][ny] == 0) continue;
        if(state[nx][ny].y == EMPTY){
          state[nx][ny] = new Pair(curtime+1,curcolor);
          q.add(new Pair(nx,ny));
        }
        else if(state[nx][ny].y == RED){
          if(curcolor == GREEN && state[nx][ny].x == curtime+1){
            cnt++;
            state[nx][ny].y = FLOWER;
          }
        }
        else if(state[nx][ny].y == GREEN){
          if(curcolor == RED && state[nx][ny].x == curtime+1){
            cnt++;
            state[nx][ny].y = FLOWER;
          }        
        }
      }
    }
    return cnt;
  }

  static void select_r(int idx){
    if(idx == r){
      mx = Math.max(mx, solve());
      return;
    }
    int cur = 0;
    if(idx != 0) cur = chosen_r[idx-1]+1;
    while(cur < candsz){
      if(isused[cur]){
        cur++;
        continue;
      }
      isused[cur] = true;
      chosen_r[idx] = cur;
      select_r(idx+1);
      isused[cur] = false;
      cur++;
    }
  }
  static void select_g(int idx){
    if(idx == g){
      select_r(0);
      return;
    }
    int cur = 0;
    if(idx != 0) cur = chosen_g[idx-1]+1;
    while(cur < candsz){
      isused[cur] = true;
      chosen_g[idx] = cur;
      select_g(idx+1);
      isused[cur] = false;
      cur++;
    }
  }
  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    g = Integer.parseInt(st.nextToken());
    r = Integer.parseInt(st.nextToken());
    board = new int[n][m];
    for(int i = 0; i < n; i++){
      st = new StringTokenizer(br.readLine(), " ");
      for(int j = 0; j < m; j++){
        board[i][j] = Integer.parseInt(st.nextToken());; 
        if(board[i][j] == 2){
          candx[candsz] = i;
          candy[candsz] = j;
          candsz++;
        } 
      } 
    }
    select_g(0);

    bw.write(Integer.toString(mx) + "\n");
    br.close();
    bw.close();
  }
  static class Pair{
    public int x, y;
    Pair(int x, int y){
      this.x = x;
      this.y = y;
    }
    Pair(){
      this.x = 0;
      this.y = 0;
    }
  }
}

Python (백트래킹)

import sys
from collections import deque
input = sys.stdin.readline

EMPTY, GREEN, RED, FLOWER = 0, 1, 2, 3
n,m,g,r = 0, 0, 0, 0
board = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
cand = [] # 좌표를 담을 에정
candsz = 0
isused = [False]*10
chosen_g = [0]*5
chosen_r = [0]*5
mx = 0

# popleft, append
def solve():
  cnt = 0
  state = [[[0]*2 for i in range(m)] for j in range(n)]
  q = deque()

  for i in range(g):
    state[cand[chosen_g[i]][0]][cand[chosen_g[i]][1]] = [0, GREEN]
    q.append(cand[chosen_g[i]])

  for i in range(r):
    state[cand[chosen_r[i]][0]][cand[chosen_r[i]][1]] = [0, RED]
    q.append(cand[chosen_r[i]])

  while q:
    cur = q.popleft()
    curtime, curcolor = state[cur[0]][cur[1]]
    if state[cur[0]][cur[1]][1] == FLOWER: continue
    for dir in range(4):
      nx = cur[0]+dx[dir]
      ny = cur[1]+dy[dir]
      if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
      if board[nx][ny] == 0: continue
      if state[nx][ny][1] == EMPTY:
        state[nx][ny] = [curtime+1,curcolor]
        q.append([nx,ny])
      elif state[nx][ny][1] == RED:
        if curcolor == GREEN and state[nx][ny][0] == curtime+1:
          cnt += 1
          state[nx][ny][1] = FLOWER
      elif state[nx][ny][1] == GREEN:
        if curcolor == RED and state[nx][ny][0] == curtime+1:
          cnt += 1
          state[nx][ny][1] = FLOWER
  return cnt

def select_r(idx):
  global mx
  if idx == r:
    mx = max(mx, solve())
    return None

  cur = 0
  if idx != 0: cur = chosen_r[idx-1] + 1
  while cur < candsz:
    if isused[cur]:
      cur += 1
      continue
    isused[cur] = True
    chosen_r[idx] = cur
    select_r(idx+1)
    isused[cur] = False
    cur += 1

def select_g(idx):
  if idx == g:
    select_r(0)
    return None

  cur = 0
  if idx != 0: cur = chosen_g[idx-1] + 1
  while cur < candsz:
    isused[cur] = True
    chosen_g[idx] = cur
    select_g(idx+1)
    isused[cur] = False
    cur += 1

n,m,g,r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
  for j in range(m):
    if board[i][j] == 2:
      cand.append([i,j])
candsz = len(cand)
select_g(0)
sys.stdout.write(str(mx)+"\n")

Python (itertools.combinations)

import sys
from collections import deque
import itertools
input = sys.stdin.readline

EMPTY, GREEN, RED, FLOWER = 0, 1, 2, 3
n,m,g,r = 0, 0, 0, 0
board = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

cand = [] # 좌표를 담을 에정
candsz = 0
chosen_g = [0]*5
chosen_r = [0]*5
mx = 0

# popleft, append
def solve():
  cnt = 0
  state = [[[0]*2 for i in range(m)] for j in range(n)]
  q = deque()

  for i in range(g):
    state[cand[chosen_g[i]][0]][cand[chosen_g[i]][1]] = [0, GREEN]
    q.append(cand[chosen_g[i]])
  
  for i in range(r):
    state[cand[chosen_r[i]][0]][cand[chosen_r[i]][1]] = [0, RED]
    q.append(cand[chosen_r[i]])

  while q:
    cur = q.popleft()
    curtime, curcolor = state[cur[0]][cur[1]]
    if state[cur[0]][cur[1]][1] == FLOWER: continue
    for dir in range(4):
      nx = cur[0]+dx[dir]
      ny = cur[1]+dy[dir]
      if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
      if board[nx][ny] == 0: continue
      if state[nx][ny][1] == EMPTY:
        state[nx][ny] = [curtime+1,curcolor]
        q.append([nx,ny])
      elif state[nx][ny][1] == RED:
        if curcolor == GREEN and state[nx][ny][0] == curtime+1:
          cnt += 1
          state[nx][ny][1] = FLOWER
      elif state[nx][ny][1] == GREEN:
        if curcolor == RED and state[nx][ny][0] == curtime+1:
          cnt += 1
          state[nx][ny][1] = FLOWER
  return cnt

n,m,g,r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
  for j in range(m):
    if board[i][j] == 2:
      cand.append([i,j])
candsz = len(cand)

for c1 in itertools.combinations(range(candsz), g+r):
  for c2 in itertools.combinations(range(g+r), g):
    ridx, gidx = 0, 0
    for i in range(g+r):
      if i in c2:
        chosen_g[gidx] = c1[i]
        gidx += 1
      else:
        chosen_r[ridx] = c1[i]
        ridx += 1
    mx = max(mx, solve())

sys.stdout.write(str(mx)+"\n")