[모의 SW 역량테스트] 2105. 디저트 카페

[모의 SW 역량테스트] 디저트 카페

---

1. 이해하기

• 디저트 카페 투어는 어느 한 카페에서 출발하여 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
• 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
• 하나의 카페에서 디저트를 먹는 것도 안 된다.
• 왔던 길을 다시 돌아가는 것도 안 된다.
• 디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 구하는 문제.
• 완전 탐색 문제이다.

---

2. 구현하기

• 디저트 카페 투어는 대각선 방향으로 움직여야 한다.

  • 사각형 모양을 그려야 하고, 출발한 카페로 돌아와야 하는 조건이 있다. 또한, 하나의 카페에서 디저트를 먹는 것이 안된다는 조건이 있으므로 디저트 카페 투어 수는 4 이상이 되어야 한다.
  • 카페 투어를 하는 방향을 일정하게 만든다. 오른쪽 아래 방향부터 시작해서 그 다음에 갈 수 있는 방향을 제한하는 것이다.
  • 같은 디저트를 먹지 않기 위해서 이미 먹은 디저트를 체크한다.

  int dfs(int sx, int sy, int d, int cx, int cy, int cnt) {
      if(cnt >= 4 and sx-1 == cx and sy+1 == cy) {
          return cnt;
      }
  
      int ret = -1;
      for(int i = d; i < 4; i++) {
          int nx = cx+dx[i], ny = cy+dy[i];
          if(nx < 0 or nx >= N or ny < 0 or ny >= N or abs(i-d) > 1) continue;
          if(dessert[map[nx][ny]]) continue;
          dessert[map[nx][ny]] = true;
          ret = max(ret,dfs(sx,sy,i,nx,ny,cnt+1));
          dessert[map[nx][ny]] = false;
      }
      return ret;
  }

• 모든 칸에서 시작해보며 최댓값을 찾는다.

  int process() {
      memset(dessert,false,sizeof(dessert));
      int ret = -1;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              dessert[map[i][j]] = true;
              ret = max(ret,dfs(i,j,0,i,j,1));
              dessert[map[i][j]] = false;
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <cstring>
using namespace std;
int map[20][20];
bool dessert[101];
int dx[] = {1,-1,-1,1};
int dy[] = {1,1,-1,-1};
int N;

int abs(int a) {
    return (a<0)?-a:a;
}

int dfs(int sx, int sy, int d, int cx, int cy, int cnt) {
    if(cnt >= 4 and sx-1 == cx and sy+1 == cy) {
        return cnt;
    }

    int ret = -1;
    for(int i = d; i < 4; i++) {
        int nx = cx+dx[i], ny = cy+dy[i];
        if(nx < 0 or nx >= N or ny < 0 or ny >= N or abs(i-d) > 1) continue;
        if(dessert[map[nx][ny]]) continue;
        dessert[map[nx][ny]] = true;
        ret = max(ret,dfs(sx,sy,i,nx,ny,cnt+1));
        dessert[map[nx][ny]] = false;
    }
    return ret;
}

int process() {
    memset(dessert,false,sizeof(dessert));
    int ret = -1;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            dessert[map[i][j]] = true;
            ret = max(ret,dfs(i,j,0,i,j,1));
            dessert[map[i][j]] = false;
        }
    }
    return ret;
}

void input() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << process() << '\n';
    }
    return 0;
}