2105 디저트 카페

#include <stdio.h>
#include <string.h>
 
using namespace std;
 
int width;
int place[30][30];
int flag[30][30];
int desert[105];
int dx[5] = { 0, -1, 1, 1, -1 };
int dy[5] = { 0, 1, 1, -1, -1 };
int rst_max;
 
void dfs(int y, int x, int dir);    // 1:좌하  2:우하  3:우상  4:좌상
void print_flag();
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        scanf("%d", &width);
        memset(place, 0, sizeof(place));
        memset(flag, 0, sizeof(flag));
        memset(desert, 0, sizeof(desert));
        rst_max = -1;
 
        for (int i = 1; i <= width; i++) 
            for (int j = 1; j <= width; j++) 
                scanf("%d", &place[i][j]);
        
        for (int i = 1; i <= width; i++) 
            for (int j = 1; j <= width; j++) {
                flag[i][j] = -1;            
                int d = place[i][j];
                desert[d] = 1;
 
                dfs(i, j, 0);
                
                flag[i][j] = 0;
                desert[d] = 0;
            }
        
        printf("#%d %d\n", t, rst_max);
    }
}
 
// 1:좌하  2:우하  3:우상  4:좌상
void dfs(int y, int x, int dir) {
    if (y > width || y <= 0 || x > width || x <= 0)
        return;
 
    for (int i = 4; i >= 1; i--) {
        // 처음 시작일때
        if (dir == 0)
            if ((i == 2) ||(i == 3) || (i == 4))
                continue;
        // 좌하 일때
        if (dir == 1)
            if ((i == 3) || (i == 4))
                continue;
        // 우하 일때
        if (dir == 2)
            if ((i == 1) || (i == 4))
                continue;
        // 우상 일때
        if (dir == 3)
            if ((i == 1) || (i == 2))
                continue;
        // 좌상 일때
        if (dir == 4)
            if ((i == 1) || (i == 2) || (i == 3))
                continue;
 
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        // 출발 지점에 도착했을 경우, 멈춘다
        if (flag[yy][xx] == -1) {
            int total_v = 0;
            for (int i = 1; i <= 101; i++)
                if (desert[i] != 0)
                    total_v += 1;
 
            if (total_v > rst_max)
                rst_max = total_v;
            return;
        }
        if (flag[yy][xx] == 1)
            continue;
 
        // 출발 지점이 아닐경우, 그대로 계속 dfs 를 진행한다
        int d = place[yy][xx];
        if (desert[d] == 0) {
            flag[yy][xx] = 1;
            desert[d] = 1;
 
            dfs(yy, xx, i);
 
            desert[d] = 0;
            flag[yy][xx] = 0;
        }        
    }
}

1시간정도 걸렸다

dfs 를 활용하는 문제였다

dfs 1개만 사용하면 되는 문제여서, 그 전 문제들보다는 쉬운 편이었다