SWEA 2105: 디저트 카페 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

대각선으로 좌표를 이동하도록 DFS를 구현해주면 된다.

그래프 문제를 풀이할 때 접해봤던 유형으로, 노드에서 사용되었던 숫자를 다시 사용하지 않으면서, 출발지점으로 되돌아가는 데에 필요한 이동 횟수를 구해주면 된다.

이 문제에서는 그러한 경우의 최솟값을 구해주면 되겠다.

그리고 사각형을 이루어야 한다는 것을 생각해서 구현해주면 되겟다.

이 부분은 코드의 주석으로 확인할 수 있다.

DFS를 진행할 때, 일반적으로 방문했던 지점은 다시 방문하지 않도록 처리한다. 또한, 이 문제의 경우, 시작지점에서 사용했던 숫자는 무조건 사용했다는 처리가 되어있기 때문에, 이미 사용했던 숫자라고 하더라도, 그 지점이 시작 지점일 경우 함수 진입을 허용해주도록 구현해야 한다.

본인은 구현을 하다보니, 시작 지점을 방문처리 하지 않고 시작한 이후에, 다음 목적지가 출발 지점이라면 방문을 허용하도록 하는 방식으로 구현했다.

이렇게 구현할 것이라면 시작 지점도 다른 지점처럼 사전에 방문처리 해주더라도 상관이 없을 것이다.

 
#include<iostream>
#include<vector>
using namespace std;
 
typedef pair<int, int> pii;
const int dr[4] = { 1, 1, -1, -1 };
const int dc[4] = { 1, -1, -1, 1 };
int n, map[21][21];
bool vis[21][21], used[101];
 
pii src;
vector<int> arr;
int Max = -1;
void dfs(pii cur, int dir, int cnt) {
 
    if (cur.first == src.first && cur.second == src.second && cnt > 1) { //시작점으로 바로 되돌아가는 경우 방지
        if (Max < cnt) Max = cnt;
        return;
    }
 
 
    for (int i = 0; i < 2; i++) { //그대로 가거나 꺾거나
 
        if (dir + i >= 4) //이 이상 회전하는 것은 사각형이 아니다
            break;
 
        int nr = cur.first + dr[dir + i];
        int nc = cur.second + dc[dir + i];
    
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
 
        if (!vis[nr][nc] && !used[map[nr][nc]]) {
 
            used[map[nr][nc]] = true;
            //arr.push_back(map[nr][nc]);
            dfs({ nr, nc }, dir + i, cnt + 1);
            //arr.pop_back();
            vis[nr][nc] = false;
            used[map[nr][nc]] = false;
 
        }
        else if (nr == src.first && nc == src.second)
            dfs({ nr, nc }, dir + i, cnt + 1);
    }
}
 
int main(void) {
    //    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        //cout << '\n';
 
        for (int i = 0; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                src.first = i;
                src.second = j;
 
                used[map[i][j]] = true; // 출발 숫자 사용처리
                //vis[i][j] = true; 시작지점 방문처리 하지 않음 나중에 다시 돌아와야 하니까
 
                //arr.push_back(map[i][j]); //어떤 노드를 방문했는지 디버깅하기 위한 용도 
 
                dfs({ i, j }, 0, 0); //좌표, 방향, 거쳐간 노드수, 방향전환횟수
 
                used[map[i][j]] = false;
                arr.clear();
 
            }
        }
 
        cout << "#" << tc << ' ' << Max << '\n';
        Max = -1;
 
    }
    return 0;
}