[C++] SWEA 2105 - 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=2105&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 디저트 카페 지역을 입력받는다.

2. 디저트를 가장 많이 먹을 수 있는 경로의 디저트 수를 출력한다.

 

<해법>

1. 문제를 접근하는 순서

=> 모든 경로를 다 탐색해 보아야 합니다. 그래서, 저는 재귀를 이용하여 구현하겠다고 생각하였습니다. 또한, 시뮬레이션 문제는 조건에 맞는 정확한 구현이 중요합니다. 따라서, 재귀를 이용하고 조건을 정확히 구현하는데 초점을 두었습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dx[] = {-1, 1, 1, -1};
int dy[] = {1, 1, -1, -1};
int N;
int map[20][20];
bool visited[101];
int startX, startY;
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
void eatDessert(int x, int y, int dir, int count) {
 
    //방향 초과 -> 종료
    if (dir > 3) return;
 
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    //직사각형 완료 -> 정답 갱신 후 종료
    if (nx == startX && ny == startY && dir == 3) {
        answer = max(answer, count);
        return;
    }
 
    //범위를 벗어난 경우 or 해당 디저트를 먹은 경우 -> 종료
    if (!isInner(nx, ny) || visited[map[nx][ny]]) return;
 
    visited[map[nx][ny]] = true;
    eatDessert(nx, ny, dir, count + 1);        //현재 방향 유지
    eatDessert(nx, ny, dir + 1, count + 1);    //다음 방향 꺾기
    visited[map[nx][ny]] = false;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        startX = 0, startY = 0;
        answer = -1;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[map[i][j]] = true;
                startX = i, startY = j;
                eatDessert(i, j, 0, 1);
                visited[map[i][j]] = false;
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

재귀함수와 구현에 대해 알아볼 수 있는 문제였습니다.