[SWEA] 2105. 디저트 카페

문제 접근

1. DFS 문제이다.

2. 대각선 방향으로 이동하며 해당 위치에 있는 디저트 번호를 확인한 뒤 방향을 바꾸거나 계속해서 같은 방향으로 가며 번호를 확인하는 과정을 반복한다.
   이때 동일한 디저트 번호는 방문할 수 없는데, is_visit 배열을 이용하여 이를 구현하였다.

3. 디저트 카페 투어는 총 4번 방향을 바꿔 출발한 곳으로 돌아와야만 정상적으로 완료된다. 이 부분이 문제의 핵심이다.
   dfs함수의 인자로 방향을 나타내는 dir를 주고 이 방향이 마지막 방향을 나타내고, 현재 위치가 출발지점과 동일하면 탐색을 종료하게 했다.

4. 방향 전환은 총 2가지 종류가 가능하다.
   현재 위치에서 두 가지 방향으로 모두 이동해 보면서 정답을 찾도록 했다.
   dfs 함수를 서로 다른 인자를 주어 두 번 호출하는 부분이 존재하는 이유이다.

풀이

#include <iostream>
#include <algorithm>

using namespace std;

int T, N, rst, sx, sy;
int map[21][21];
int is_visit[101];
int dy[] = { 1, -1, -1, 1 };
int dx[] = { 1, 1, -1, -1 };

int is_range(int x, int y) {
    if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
    return false;
}

void dfs(int x, int y, int dir, int cnt) {
    if (dir == 3 && sx == x && sy == y) {
        rst = max(rst, cnt);
        return;
    }
    if (!is_range(x, y) || is_visit[map[x][y]]) return;
    
    is_visit[map[x][y]] = 1;

    dfs(x + dx[dir], y + dy[dir], dir, cnt + 1);
    dfs(x + dx[dir + 1], y + dy[dir + 1], dir + 1, cnt + 1);
    
    is_visit[map[x][y]] = 0;
}

void slove() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            sx = i;
            sy = j;
            dfs(i, j, 0, 0);
        }
    }
}

void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    rst = -1;
}

int main() {
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        input();
        slove();
        cout << "#" << tc + 1 << " " << rst << endl;
    }
}