SWEA 모의 역량 테스트 2105 디저트 카페

SW Expert Academy

자료구조

• cake : 각 디저트를 먹었는지 체크
• visit : 각 칸을 방문했는지 페크

풀이

1. 각 칸마다 dfs를 돌린다 ⇒ 돌린 후, 첫 칸에 대한 cake과 visit을 초기화!
2. dfs 파라미터
   • y, x, dir은 현재 좌표와 이동방향
   • sy, sx는 시작점
   • cnt는 디저트를 몇 개 먹었는가 (depth)
   • change는 방향을 몇 번 꺾었는가 (사각형을 만들려면 총 3회꺾어야 함)
3. DFS의 조건문

   • 세 번 꺾은 후 출발점으로 되돌아온 경우 if(change==3 && y==sy && x==sx)

   • 범위 초과, 이미 방문, 이미 먹은 디저트 ⇒ return

   • 출발점 : cake와 visit을 갱신해 준 후 다음 칸으로 재귀호출 (방향전환 x)

   • 출발점이 아닐 경우

     1. 그대로 : 원래 진행 방향으로 재귀호출

     2. 방향 전환 : change를 올려준 후 그 다음 방향으로 : 0번 꺾었으면 1번방향으로 1번 꺾었으면 2번방향으로

      

#include <iostream>
using namespace std;
int n;
int map[25][25];
int cake[105];
int visit[25][25];
int dy[]={1, 1, -1, -1};
int dx[]={1, -1, -1, 1};
int ans;
void init() {
    ans = 0;
}
void dfs(int y, int x, int dir, int sy, int sx, int cnt, int change) {
    // 돌아옴(종료)
    if(change==3 && y==sy && x==sx) {
        if(cnt>ans) {
            ans = cnt;
        }
        return;
    }
    if(y<0 || x<0 || y>n-1 || x>n-1) return;
    if(visit[y][x]) return;
    if(cake[map[y][x]]) return;

    // 초기
    if(y==sy && x==sx) {
        cake[map[y][x]] = 1;
        visit[y][x] = 1;
        dfs(y+dy[dir], x+dx[dir], dir, sy, sx, cnt+1, change);
    }
    else {
        cake[map[y][x]] = 1;
        visit[y][x] = 1;
        int ny; int nx;
        // 그대로!
        ny=y+dy[dir];
        nx=x+dx[dir];
        dfs(ny, nx, dir, sy, sx, cnt+1, change);
        // 방향 전환
        ny=y+dy[dir+1];
        nx=x+dx[dir+1];
        dfs(ny, nx, dir+1, sy, sx, cnt+1, change+1);

        // 변수 초기화
        cake[map[y][x]] = 0;
        visit[y][x] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for(int tc=1; tc<=T; tc++) {
        cin >> n;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                cin >> map[i][j];
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                dfs(i, j, 0, i, j, 0, 0);
                cake[map[i][j]] = 0;
                visit[i][j] = 0;
            }
        }
        if(ans>0) cout<<'#'<<tc<<' '<<ans<<'\n';
        else cout<<'#'<<tc<<' '<<-1<<'\n';
        init();
    }

    return 0;
}