[SWEA] 2105. 디저트 카페

안녕? 나는 응애개발자

 

 

오늘은 좀 화가 나있다. 왜냐면....

나는 맥을 이용하는데, 맥 터미널로 돌리면 잘만 나오는 결과가 SWEA에서 돌리기만 하면 이상한 것이다.

 

평소에 init_()이란 함수를 만들어 일일이 초기화를 했는데, 실패했다.

삽질하다가 memset을 이용했는데 성공적으로 잘만됐다.

 

화가 났다.

 

고작 초기화 때문에 30분을 삽질했다는 이 사실이!!!

한번에 통과할 수 있었는데 2번만에 통과한 이 사실이!!!!!!!!!!!

 

오늘 문제는 완탐(dfs)를 사용해서 풀면 되는 간단한 문제였다.

코드 리뷰, 시작!

#include <iostream>
#include <cstring>

using namespace std;

int N;
int map[20][20];
int chk[20][20];	//갔던곳은 안가기위한 배열
int dessert[101];	//먹은 디저트는 안먹기 위한 배열
int ans;	

pair<int, int> start;	//처음좌표를 저장할 pair

int dy[4] = {1,1,-1,-1};	//하우->하좌->상좌->상우
int dx[4] = {1,-1,-1,1};


//맵의 범위를 체크하는 함수
bool check(int y, int x){
    if((y>=0) && (x>=0) && (y<N) && (x<N))
        return true;
    return false;
}

//완탐
void dfs(int y, int x, int prev, int cnt){
	//사각형을 만들고 처음자리에 왔다면
    if((cnt>1) && (start.first==y) && (start.second==x)){
        ans = max(ans, cnt);
        return;
    }
    
    //현재 좌표 왔다고 체크해주기
    chk[y][x] = 1;
    dessert[map[y][x]] = 1;

    for(int i=0; i<2; i++){
    
    	//prev+i를 하면 사각형을 만들면서 가겠죠?
        int ny = y + dy[prev + i];
        int nx = x + dx[prev + i];    
        
	//맵 안에 있고, 가본적없고, 먹어본적 없는 디저트를 팔고있는 카페라면
        if(check(ny,nx) && chk[ny][nx]==0 && dessert[map[ny][nx]]==0){
            dfs(ny,nx,prev+i,cnt+1);
        }
        
        //초기좌표라면    
        else if(start.first==ny && start.second==nx)
            dfs(ny,nx,prev+i,cnt+1);
    }
    
    //완탐이니까 왔던곳은 되돌려주기
    chk[y][x] = 0;
    dessert[map[y][x]] = 0;
}

int main(int argc, char** argv){
    int test_case;
    cin>>test_case;
    for(int T=1; T<=test_case; T++){
    
        //화가났던 초기화 부분, 앞으로 memset만 사용할거임 화가나 화가.
        ans = -1;
        memset(dessert, 0, sizeof(dessert));
        
        cin>>N;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                cin>>map[i][j];
                chk[i][j] = 0;
            }
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                start.first = i;
                start.second = j;
                dfs(i,j,0,0);
            }
        }
        cout<<"#"<<T<<" "<<ans<<endl;
    }
    return 0;
}