2105.디저트 카페

이번에 풀어볼 문제는 SW Expert 2105번 디저트 카페이다. 재귀함수를 이용해서 풀면 간단히 풀리지만

중요한건 역시나 설계이다. 어떻게하면 불필요한 계산을 줄일지 고민해보고 풀어야한다.

SW Expert Academy

1. 각 모서리 값은 굳이 탐색을 할 필요가 없다

=> 우리가 탐색하는 형태는 마름모 모양이므로 각 모서리는 탐색을 할 수 없다는 것을 인지

 

2. 항상 탐색의 시작은 아래로만 탐색하면된다. => Point !!

=> 탐색은 왼쪽에서 오른쪽으로, 윗줄부터 아랫줄로 탐색이 진행되는데 그림을 그려보면 알겠지만

     윗줄에서 탐색한 내용들은 전부 아랫줄에서 위로 탐색하는 부분과 일치한다. 그러므로 불필요한 연산이다.

 

3. 탐색방향에 대한 생각  => Point !!

=> 그렇다면 우리가 탐색을 시작하는 건 무조건 아랫쪽방향인데 그렇게는 두 가지가 있다. 바로 시계냐 반시계냐 인데

     이 또한 그림을 그려서 생각해보면 방향이 상관이 없다는 것을 알 수 있다.

 

4. 중복은 배열의 인덱스로 체크해주자! 

=> 다양한 문제를 풀어보았다면 한 번쯤은 마주치게되는 스킬이다. 해당 배열의 값을 인덱스로 중복되지 않았는지 check!!

 

=> 개인적으로 2, 3번을 떠올리는게 Key point 같다.

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <string.h>
#include <algorithm>
 
#define MAX 21
#define MAX2 101
 
using namespace std;
 
int T, N;
int map[MAX][MAX]; // 디저트 map
bool check[MAX2]; // 갔던 카페인지 확인하기 위한 배열
 
int dx[4] = { 1, 1, -1, -1 }; // 대각선 방향 => 시계방향
int dy[4] = { 1, -1, -1, 1 };
 
int start_x, start_y; // 탐색 시작 좌표
int answer = -1; // 정답
 
void search(int x, int y, int dir, int cnt){// y, x 좌표, 탐색방향의 idx, 탐색한 카페 갯수
    int ax = x + dx[dir]; // 대각선이동
    int ay = y + dy[dir];
 
    if (ax < 0 || ay < 0 || ax >= N || ay >= N) // 맵에서 벗어나면 return
        return;
 
    if (ax == start_x && ay == start_y && dir == 3){ // 초기의 값으로 돌아오거나 대각선 탐색 idx를 모두 사용한 경우
                                                     // 이렇게 하는 이유는 idx를 조건으로 안주면 왔던길을 되돌아오는걸 걸러낼수 없음
        answer = max(answer, cnt); // 최대 값을 구하고 리턴
        return;
    }
 
    
    if (!check[map[ax][ay]]){ // 간적이 없는 길인 경우
        check[map[ax][ay]] = true; // 간것으로 표기
        search(ax, ay, dir, cnt + 1); // 탐색 대각선 방향은 그대로해서 탐색 진행
 
        if (dir < 3) // 탐색 방향을 모두 사용하지 않았다면
            search(ax, ay, dir + 1, cnt + 1);  // 탐색방향을 바꿔서 다시 탐색 진행
        
        check[map[ax][ay]] = false; // 다른 방향을 찾기위해 갔던길은 다시 false
    } 
}
void init(){ // 초기화 함수
    answer = -1;
    memset(map, 0, sizeof(map));
    memset(check, 0, sizeof(check));
}
int main()
{
    freopen("2105.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init(); // 초기화
 
        cin >> N;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j]; // 입력을 받음
                if ((i == 0 || i == N-1) && (j == 0 || j == N - 1)) // 각 모서리의 경우 
                    map[i][j] = 0; // 탐색하지 않기위해 0으로 초기화
            }
        }
 
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (map[i][j]){ // map에 값이 있을 때만 탐색
                    start_x = i;// 탐색 시작 초기좌표 저장
                    start_y = j;
                    check[map[i][j]] = true; // 탐색 시작의 디저트 번호는 방문으로 체크
                    search(i, j, 0, 1); // 탐색 시작
                    check[map[i][j]] = false;// 다른 탐색을 위해 다시 방문 해제
                }
            }
        }    
        cout << "#" << z << " " << answer << endl;
    }
    return 0;
}