3개 놓는 경우의 수 다 찾아서!!!
문제에서 말한 MIN 값 찾으면 됨!!
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 87 88 89 90 91 92 93 94 95 96 97 98 | #include <stdio.h> #include <string.h> typedef struct { int y, x; }point; int N, map[13][13], MIN, visit[13][13]; int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; point Q[3]; int Charge() { int total = 0; int V[13][13] = { 0, }; for (int a = 0; a < 3; a++) { int x = Q[a].x; int y = Q[a].y; total += map[y][x]; V[y][x] = 1; for (int i = 0; i < 4; i++) { int yy = y + dy[i]; int xx = x + dx[i]; if (map[yy][xx] == -1 || V[yy][xx] == 1) return 987654321; total += map[yy][xx]; V[yy][xx] = 1; } } return total; } void DFS(int y, int x, int num) { if (num == 3) { int Total = Charge(); if (Total < MIN) MIN = Total; return; } for (int i = y; i < N; i++) { for (int j = x; j < N; j++) { if (visit[i][j] == 0) { visit[i][j] = 1; Q[num].y = i; Q[num].x = j; DFS(i, j, num + 1); Q[num].x = 0; Q[num].y = 0; visit[i][j] = 0; } } x = 2; } return; } int main() { MIN = 987654321; memset(map, -1, sizeof(map)); memset(visit, 0, sizeof(visit)); scanf("%d", &N); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &map[i][j]); } } DFS(2, 2, 0); printf("%d\n", MIN); return 0; } | cs |
'SW 업무 관련 > 백준' 카테고리의 다른 글
[C언어] 14501. 퇴사 (0) | 2018.10.09 |
---|---|
[C언어] 9207. 페그 솔리테어 (0) | 2018.10.03 |
[C언어] 15683. 감시 (0) | 2018.09.26 |
[C언어] 3108. 로고 (0) | 2018.09.26 |
[C언어] 10164. 격자상의 경로 (0) | 2018.09.25 |