[DFS] SWEA2105 디저트 카페

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

 

Solution

• DFS하면서 지나온 디저트 카페를 path에 넣고, 중복되지 않은 카페들을 방문해간다.

Point

• 중복을 피하는 것은 어렵지 않지만, 직사각형 모양의 cycle을 만들어야 한다는 조건이 까다롭다.
• 카페를 방문할 수 있는 조건: 맵 안에 있으면서, 방문한 적이 없고, 중복되지 않으면서 4번 이상 방향을 전환하지 않았을 때
• 불필요한 탐색을 없애기 위해, 처음과 마지막 턴 이후의 탐색은 한쪽 방향으로만 하도록 했다.
• 방향을 강제할 때, 주의할 점은 map[x][y] 형식으로 만들면 실제로는 x가 세로고 y가 가로이기 때문에 dx[4], dy[4] 방향을 잘 정해줘야 한다.
• 문제 조건에 따라 반드시 4개 이상의 노드를 지나도록 사각형을 만들어야 한다.

---

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int T, N;
int result;
int dx[4] = { 1, 1, -1, -1 }; //↘ ↙ ↖ ↗ 
int dy[4] = { 1, -1, -1, 1 };//↘ ↙ ↖ ↗
vector<int> path;
int map[20][20];
bool visited[20][20];

void input() {
    result = -1;
    memset(visited, false, sizeof(visited));
    memset(map, 0, sizeof(map));
    path.clear();
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

bool IsPassed(int d) {
    for (int i = 0; i < path.size(); i++) {
        if (d == path[i])
            return true;
    }
    return false;
}

void dfs(int sx, int sy, int cx, int cy, int dir, int nTurn) {
    visited[cx][cy] = true;
    path.push_back(map[cx][cy]);

    for (int i = 0; i < 4; i++) {
        if (sx == cx && sy == cy && i != 0) continue; //first step: go to South East only (↘)
        if (nTurn == 3 && i != 3) continue; //After two turn: go to North East only (↗)

        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if (nx == sx && ny == sy && path.size() > 3) { //cycle
            result = max(result, (int)path.size());
        }
        if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && !IsPassed(map[nx][ny]) && nTurn < 4) {
            if (dir != i) //turn
                dfs(sx, sy, nx, ny, i, nTurn + 1);
            else
                dfs(sx, sy, nx, ny, i, nTurn);
            path.pop_back();
            visited[nx][ny] = false;
        }
    }
}

void dfsAll() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N-1; j++) {
            path.clear();
            memset(visited, false, sizeof(visited));
            dfs(i, j, i, j, 0, 0);
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        input();
        dfsAll();
        cout << "#" << t << " " << result << endl;
    }
}