코테 노트/SWEA

SWEA2105 [모의 SW 역량테스트] 디저트 카페 C++

화요밍 2021. 10. 19. 19:22
728x90
반응형

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

최종 코드

 

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

SWEA 알고리즘 소스 코드 모음. Contribute to hwayeon351/SWEA-Algorithms development by creating an account on GitHub.

github.com

#include <iostream>
#include <cstring>
using namespace std;

int N;
int desert[20][20] = { 0, };
int visit[101] = { 0, };
int dr[4] = { 1, 1, -1, -1 };
int dc[4] = { -1, 1, 1, -1 };

int answer = -1;

void init() {
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> desert[r][c];
		}
	}
	answer = -1;
}

void go_cafe() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			for (int d1 = 1; d1 <= N - 2; d1++) {
				for (int d2 = 1; d2 <= N - 2; d2++) {
					memset(visit, 0, sizeof(visit));
					int nr = r;
					int nc = c;
					int cnt = 1;
					visit[desert[nr][nc]] = 1;
					bool check = true;

					for (int d = 0; d < d1; d++) {
						nr += dr[0];
						nc += dc[0];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d2; d++) {
						nr += dr[1];
						nc += dc[1];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d1; d++) {
						nr += dr[2];
						nc += dc[2];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d2-1; d++) {
						nr += dr[3];
						nc += dc[3];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					if (answer == -1 || answer < cnt) answer = cnt;
				}
			}
		}
	}
}

int main()
{
	int T;
	cin >> T;

	for (int test_case = 1; test_case <= T; test_case++) {
		init();
		go_cafe();

		cout << "#" << test_case << " " << answer << "\n";
	}

	return 0;
}

풀이 과정

풀이 시간 30분

#include <iostream>
#include <cstring>
using namespace std;

int N;
int desert[20][20] = { 0, };
int visit[101] = { 0, };
int dr[4] = { 1, 1, -1, -1 };
int dc[4] = { -1, 1, 1, -1 };

int answer = -1;

void init() {
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> desert[r][c];
		}
	}
	answer = -1;
}

void go_cafe() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			for (int d1 = 1; d1 <= N - 2; d1++) {
				for (int d2 = 1; d2 <= N - 2; d2++) {
					memset(visit, 0, sizeof(visit));
					int nr = r;
					int nc = c;
					int cnt = 1;
					visit[desert[nr][nc]] = 1;
					bool check = true;

					for (int d = 0; d < d1; d++) {
						nr += dr[0];
						nc += dc[0];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d2; d++) {
						nr += dr[1];
						nc += dc[1];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d1; d++) {
						nr += dr[2];
						nc += dc[2];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					for (int d = 0; d < d2-1; d++) {
						nr += dr[3];
						nc += dc[3];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[desert[nr][nc]]) {
							check = false;
							break;
						}
						cnt++;
						visit[desert[nr][nc]] = 1;
					}
					if (!check) continue;

					if (answer == -1 || answer < cnt) answer = cnt;
				}
			}
		}
	}
}

int main()
{
	int T;
	cin >> T;

	for (int test_case = 1; test_case <= T; test_case++) {
		init();
		go_cafe();

		cout << "#" << test_case << " " << answer << "\n";
	}

	return 0;
}

이전 풀이

풀이 시간 1시간 24분

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int N;
int desert[21][21] = {0, };

//디저트 카페 투어를 하면서 먹은 디저트 종류 체크
int visit[101] = {0, };

//0-왼쪽 아래, 1-오른쪽 아래, 2-오른쪽 위, 3-왼쪽 위
int dx[4] = {-1, 1, 1, -1};
int dy[4] = {1, 1, -1, -1};

int max_deserts = -1;

void go_tour(){
    int nx, ny, cnt;
    bool check;
    
    //방향 0->1->2->3 순서대로 투어를 진행한다
  	//d1 = 방향 0, 2일 때 가야하는 거리
    //d2 = 방향 1, 3일 때 가야하는 거리
 	//가능한 모든 d1, d2 조합으로, 모든 (x, y) 위치에서 디저트 투어를 진행한다
    for(int d1=1; d1<=N-1; d1++){
        for(int d2=1; d2<=N-1; d2++){
            for(int y=0; y<N-1; y++){
                for(int x=1; x<N-1; x++){
                	//디저트 투어 전 visit 배열 초기화
                    memset(visit, 0, sizeof(visit));
                    nx = x;
                    ny = y;
                    //(x, y)에 있는 디저트 종류를 먹었으므로 카운팅하고 방문 처리한다
                    cnt = 1;
                    visit[desert[y][x]] = 1;

                    //check = true -> 디저트 카페 투어가 가능한 경우, check = false -> 디저트 카페 투어가 불가능한 경우
                    check = true;
                    
                    //투어 시작
                    for(int i=0; i<4; i++){
                        int d;
                        //각 방향에 대해 가야하는 거리 값 d를 설정
                        if(i==0) d=d1;
                        else if(i==1) d=d2;
                        else if(i==2) d=d1;
                        else d=d2-1;
                        
                        //d만큼 한 칸씩 움직이면서 디저트를 먹는다
                        for(int j=0; j<d; j++){
                            nx += dx[i];
                            ny += dy[i];
                            //지역을 벗어나거나 이미 이전에 먹은 디저트 종류와 같은 경우, 디저트 카페 투어가 불가능하다
                            if(nx<0 || nx>=N || ny<0 || ny>=N || visit[desert[ny][nx]]) {
                                check = false;
                                break;
                            }
                            //해당 디저트를 방문 처리 하고 종류 카운팅
                            visit[desert[ny][nx]] = 1;
                            cnt++;
                        }
                        //디저트 투어가 불가능한 경우, 투어를 이어가지 않는다
                        if(!check) break;
                    }
                    //디저트 투어가 불가능한 경우, 다음 경우를 탐색한다
                    if(!check) continue;
                    //디저트 투어를 완료한 경우, max_deserts를 갱신한다
                    if(max_deserts < cnt) max_deserts = cnt;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        max_deserts = -1;
        cin >> N;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> desert[y][x];
            }
        }
        go_tour();
        cout << "#" << test_case << " " << max_deserts << endl;
    }
    return 0;
}
//시간복잡도 = O(N^4), 공간복잡도 = O(N^2)

 

728x90
반응형

'코테 노트 > SWEA' 카테고리의 다른 글

SWEA [모의 SW 역량테스트] 점심 식사시간 C++  (0) 2021.10.20
SWEA2477 [모의 SW 역량테스트] 차량 정비소 C++  (0) 2021.10.19
SWEA5650 [모의 SW 역량테스트] 핀볼 게임 C++  (0) 2021.10.18
SWEA4008 [모의 SW 역량테스트] 숫자 만들기 C++  (0) 2021.10.18
SWEA5656 [모의 SW 역량테스트] 벽돌 깨기 C++  (0) 2021.10.17

'코테 노트/SWEA'의 다른글

  • 현재글SWEA2105 [모의 SW 역량테스트] 디저트 카페 C++

관련글

댓글

티스토리툴바