Programming/Algorithm

swe 2105 디저트 카페

OKOK 2018. 4. 10. 23:03

1. dfs 에 대한 아이디어는 명확한데,

2. visit 안에서 방향을 변경하는 것과, 변경하지 않고 가능 dfs 를 쓴다는점.

3. 맵을 벗어나면 리턴을 한다는점을 명확히 알아야 합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
 
#define SIZE 22 // 22
#define SIZE2 101 // 101
int map[SIZE][SIZE];
int dx[] = { 1,1,-1,-1 };
int dy[] = { 1,-1,-1,1 };
int numArr[SIZE2];
int ans;
int maxVal;
int N;
 
void problemIn() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}
 
void init() {
    ans = 0;
    maxVal = 0;
    memset(numArr, 0, sizeof(numArr));
}
 
void dfs(int depth, int x, int y, int endX, int endY) {
 
    if (depth == 4) {
        if (x == endX && y == endY) {
            ans = 0;
            for (int i = 0; i < 101; i++) {
                if (numArr[i] == 1) {
                    ans++;
                }
            }
            maxVal = max(maxVal, ans);
            return;
        }
    }
 
    int nx = x + dx[depth];
    int ny = y + dy[depth];
 
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return;
    else {
        if (numArr[map[nx][ny]] == 0) {
            numArr[map[nx][ny]] = 1;
            dfs(depth, nx, ny, endX, endY); // 방향 유지
            dfs(depth + 1, nx, ny, endX, endY); // 방향 변경
            numArr[map[nx][ny]] = 0;
        }
        else {
            dfs(depth + 1, x, y, endX, endY); // 갈 길이 없어서 방향 변경
        }
    }
}
 
void solve() {
    for (int i = 0; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            numArr[map[i][j]] = 1;
            dfs(0, i, j, i+1, j-1);
            numArr[map[i][j]] = 0;
        }
    }
}
 
int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        problemIn();
        solve();
        if (maxVal == 0) {
            maxVal = -1;
        }
        cout << "#" << tc << " " << maxVal << endl;
        init();
    }
    return 0;
}
cs

 


저작자표시