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

문제

SWEA 모의 SW 역량테스트 - 2105 디저트 카페

SW Expert Academy

 

---

문제 풀이

접근 방식

대각선 방향으로 움직이며 사각형을 그리며 출발한 카페로 돌아오는 루트에서

디저트가 겹치지 않는 경로 중 가장 긴 경로를 찾는 문제이다.

 

어느 방향으로 움직이던 사각형을 그리기만 하면 되기 때문에 시계 방향으로 탐색을 진행하였다.

그리고 가장 윗 모서리에서부터 시작하여 사각형을 그리도록 구현할 것이기 때문에

사각형을 그릴 수 있는 시작 위치는 양 옆이 한 칸 이상 존재하고 아래로 2칸 이상이 존재해야 한다.

이를 고려하여 시작 위치를 한정하였고, 시작 위치에서 DFS 방식으로 탐색하여 가장 긴 루트를 찾아주었다.

 

DFS 함수는 위치(x, y)와 이동 방향(d)을 매개변수로 갖는 함수로 구현하였다.

우선, 다음 칸으로 이동할 수 있는지를 먼저 체크해주었다.

(map의 내부인 경우, 같은 디저트가 없는 경우에만 이동할 수 있음)

그 후, 같은 방향으로 계속 갈 경우와 다음 방향(시계 방향)으로 가는 경우로 나눠서 재귀적으로 수행해주었다.

이때, 가장 마지막 방향인 경우에는 다음 방향이 없기 때문에 같은 방향으로만 갈 수 있도록 구현해주었다.

(방향 순서 :↘(0) - ↙(1) - ↖(2) - ↗(3))

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, MAX, startX, startY;
int map[20][20];
int dir[4][2] = { {1,1},{1,-1},{-1,-1},{-1,1} };
vector<int> temp;
 
void DFS(int x, int y, int d) {
    int nx = x + dir[d][0];
    int ny = y + dir[d][1];
 
    if (d == 3 && nx == startX && ny == startY) {
        int len = temp.size();
        if (MAX < len) MAX = len;
        return;
    }
 
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return;
    if (find(temp.begin(), temp.end(), map[nx][ny]) != temp.end()) return;
    temp.push_back(map[nx][ny]);
    if (d == 3) {
        DFS(nx, ny, d);
    }
    else {
        DFS(nx, ny, d);
        DFS(nx, ny, d + 1);
    }
    temp.pop_back();
    return;
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
        memset(map, 0, sizeof(map));
        for (int i = 0; i < N; i++)  {
            for (int j = 0; j < N; j++)  {
                cin >> map[i][j];
            }
        }
 
        MAX = -1;
        for (int i = 0; i < N - 2; i++) {
            for (int j = 1; j < N - 1; j++) {
                temp.clear();
                temp.push_back(map[i][j]);
                startX = i, startY = j;
                DFS(i, j, 0);
            }
        }
        cout << "#" << test_case << " " << MAX << endl;
    }
    return 0;
}

실행 결과

실핼 결과 : Pass (371ms)