[SWEA] 2105번 디저트 카페

1953번 탈주범 검거

문제 링크

 

해결방법

DFS + 백트래킹을 이용하여 모든 경우를 탐색하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

시작노드에서 ↙︎ 방향으로 출발을 시킨다

DFS 탐색으로 해당 노드에서 그대로 이동하는 경우 , 반시계 방향으로 회전하여 이동하는 경우 로 나눠 탐색을 이어나간다

기존에는 set 을 통해 중복된 값을 체크했는데 이는 시간초과 를 발생시켰다

문제의 조건을 잘 읽어보니 디저트의 종류는 1~100 으로 정해져있었다

따라서 set 이 아닌 1차원 배열을 통해 중복된 값을 체크하여 문제를 해결할 수 있었다

 

문제의 조건

• N ≤ 20
• 디저트의 종류 ≤ 100
• 한 노드에서 출발하여 대각선 이동으로만 사이클을 형성해야한다
• 한 사이클에는 중복된 값 X
• 한 사이

 

시간 복잡도

시작 노드는 N*N 의 모든 노드가 될 수 있다

???

 

 

소스코드

문제 해결 시간 : 2h

메모리 : 12628 KB

시간 : 55 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;

int testcase;
int n,ans;
int sx,sy;
int map[21][21];
int visited[101];

int d[4][2] = {{1,-1},{1,1},{-1,1},{-1,-1}};

void dfs(int x,int y,int cnt,int dir){
    // 사이클이 형성되었다면
    if(x==sx && y==sy && dir==3){
        ans = max(ans,cnt);
        return;
    }
    
    // 방향전환을 하지 않는 경우와 하는 경우
    for(int i=1; i<=2; i++){
        int nx,ny,nd;
        
        // 방향전환을 하지 않음
        if(i==1){
            nd = dir;
            nx = x + d[nd][0];
            ny = y + d[nd][1];
        }
        // 반시계 방향으로 방향전환 수행
        else{
            // 시작노드는 방향전환 X
            if(x==sx && y==sy) continue;
            
            // 방향전환을 3번했다면 X
            if(dir == 3) continue;
            
            nd = dir + 1;
            nx = x + d[nd][0];
            ny = y + d[nd][1];
        }
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        
        // 다음 노드가 시작지점이라면
        if(nx==sx && ny==sy){
            dfs(nx,ny,cnt+1,nd);
            break;
        }
        
        // DFS 탐색
        if(!visited[map[nx][ny]]){
            visited[map[nx][ny]] = true;
            dfs(nx,ny,cnt+1,nd);
            visited[map[nx][ny]] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        cin >> n;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        memset(visited, false, sizeof(visited));
        ans = -1;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                visited[map[i][j]] = true;
                sx = i; sy = j;
                dfs(i,j,0,0);
                visited[map[i][j]] = false;
            }
        }
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}