[SW Expert Academy] 2105. [모의 SW 역량테스트] 디저트 카페 풀이 (C++)

2018. 3. 17에 쓰여진 글입니다.

---

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE

SW Expert Academy

 

풀이방법

완탐을 대각선으로 아름답게(?) 돌리면 해결..

기억속을 더듬어.. 풀이방법을 좀더 써보자면...

현재위치에서 ↘ 방향 대각선이 대각선 1, ↙방향 대각선이 대각선 2라고 하면,

0,0부터 n,n까지 모든 점을 돌면서 완탐을 돌것.

이때 각점에서 대각선1과 대각선2의 최대 길이를 구해줌

이런식으로 생각하면됨

이상황을 보면 대각선1의 최대길이는1, 대각선2의 최대길인 2가 될것.

이걸 체크하는 함수가 check_max_length 함수임.

이렇게 현재점에서 최대길이를 구한후 그점에서 사각형을 만들어보는것임. 

만약 두 대각선중 1개라도 값이 0이면 사각형이 만들어지지 않을것임. 이때는 투어자체를 하지않음

이걸 하는 코드가 바로 이부분임

 if (length_first == 0 || length_second == 0)    //대각선길이가 하나라도 0이면
                    continue;        //디저트카페 투어가 불가능하니까 패스시켜줌

바로 이런경우. 대각선1값이 0임

 

 

사각형을 만들 수 있으면,

사각형을 만들때 대각선1,2의 최대길이로 만들수있는 사각형 -> 최소크기로 만들수있는 사각형 순으로 탐색함 

즉, 이렇게 탐색된다고 보시면 됨.

탐색순서1

탐색순서2

이런식으로 주르르륵 완탐으로 다 찾으면됨.

 

 

아근데 미치겠다. 내가 내코드에 코드리뷰달고싶어지는 심정..

어케 이렇게 짜놨지.. 변수이름은 또왜저런것인가.. 로직도 바꾸고싶은 충동이 겁나게 들구 ..흑흑

2년만에 보는 코드는 참 기분이 이상하군요. ㅡ.ㅡ

참민망하지만 다시풀여력이 없으므로.. 참아보도록 합시다 ㅎㅎ..(머쓱~ 타드)

 

소스코드

#include <iostream>
#include <algorithm>        //min max 위한 헤더
 
using namespace std;
 
enum DIR { FIRST = 0, SECOND = 1 };
 
int N;                //변의길이
int map[21][21];    //맵(변의길이가20까지니까 21까지배열만들어줌)
bool visited[101];    //디저트카페 방문했는지 체크하는 배열
int dx[] = { 1,1,-1,-1 };    //대각선 돌리기
int dy[] = { 1,-1,-1,1 };
int length_first, length_second;    //대각선 길이 1,2 
int Answer;            //정답
int max_store;        //최대 디저트카페수
 
 
void Init_map()        //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = 0;
}
 
void Init_visited()    //방문초기화
{
    for (int i = 1; i <= max_store; i++)
        visited[i] = false;
}
 
void check_max_length(int cur_x, int cur_y, int dir)    //대각선 최대길이 찾기
{
    if (!visited[map[cur_x][cur_y]]) {        //해당 디저트 카페 방문안했으면
        visited[map[cur_x][cur_y]] = true;    //방문해주고
        int new_x = cur_x + dx[dir];        //대각선방향으로 진행
        int new_y = cur_y + dy[dir];        //대각선방향으로 진행
        if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < N &&    //범위안에있고
            !visited[map[new_x][new_y]]) {                        //방문안한 디저트 카페라면
            if (dir == FIRST)                //대각선1길이 증가시킴
                length_first++;
            else
                length_second++;            //대각선2길이 증가시킴
            check_max_length(new_x, new_y, dir);    //재귀로 계속들어가서 최대 길이 찾음
        }
    }
}
 
void solve(int cur_x, int cur_y)
{
    while (length_first > 0) {        //대각선1길이가 0보다 크면
        int a = length_first;        //a에 대각선1길이 저장
        int b = length_second;        //b에 대각선2길이 저장
        while (b > 0) {                //b가 0보다 클경우
            int new_x = cur_x;        //현재좌표저장해주고
            int new_y = cur_y;
            bool flag = true;        //flag를 true로 해주고
            Init_visited();            //방문초기화
            for (int i = 0; i < 4; i++) {    //대각선방향으로 돌림
                if (i == 0 || i == 2) {        //i가 0이거나 2이면 대각선1방향체크
                    for (int j = 0; j < a; j++) {    //최대길이만큼 돌림
                        new_x += dx[i];                //대각선1 방향으로
                        new_y += dy[i];
                        if (!visited[map[new_x][new_y]])        //방문안했으면
                            visited[map[new_x][new_y]] = true;    //방문해주고
                        else {        //방문된카페면 중복으로 방문이 안되기때문에
                            flag = false;    //flag를 false로 하고
                            break;            //더 투어해볼필요도없으니까 탈출
                        }
                    }
                }
                else {        //i가 1이거나 3이면
                    for (int j = 0; j < b; j++) {    //b최대길이만큼 돌림
                        new_x += dx[i];                //대각선2 방향으로 
                        new_y += dy[i];
                        if (!visited[map[new_x][new_y]])        //방문안했으면
                            visited[map[new_x][new_y]] = true;    //방문해줌
                        else {                //방문한곳이면
                            flag = false;    //더 투어해볼필요없으니까 flag를 false로 
                            break;            //탈출
                        }
                    }
                }
                if (!flag)    //flag가 false면
                    break;    //탈출
            }
            if (flag) {        //flag가 true면 투어가능하고, 사각형이 만들어진것임
                int tmp_answer = 0;
                for (int i = 1; i <= max_store; i++)    //방문한 카페 숫자 체크
                    if (visited[i])
                        tmp_answer++;
                Answer = max(Answer, tmp_answer);    //정답에 넣어줌
            }
            b--;        //b길이를 줄인다(대각선2길이를 줄임)
        }
        length_first--;    //대각선1길이를 줄임
    }
    //다돌면 완전 탐색을 한것임
}
 
int main()
{
    int T;
    cin >> T;        //테케입력받기
    for (int test_case = 1; test_case <= T; test_case++) {
        Answer = -1;        //정답초기화
        max_store = -987654321;
        cin >> N;
        Init_map();        //맵초기화
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];        //맵입력받음
                max_store = max(max_store, map[i][j]);
            }
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {    //모든 좌표에서 돌림
                length_first = 0;            //대각선1 초기화
                length_second = 0;            //대각선2 초기화
                Init_visited();                //방문초기화
                check_max_length(i, j, FIRST);    //대각선1 최대길이 찾기
                Init_visited();                //방문초기화
                check_max_length(i, j, SECOND);    //대각선2 최대길이 찾기
                if (length_first == 0 || length_second == 0)    //대각선길이가 하나라도 0이면
                    continue;        //디저트카페 투어가 불가능하니까 패스시켜줌
                solve(i, j);        //투어가 가능하다면 투어시작
            }
        cout << "#" << test_case << " " << Answer << endl;    //정답출력
    }
 
    return 0;
}