A응실 최적 경로 / 비트마스트, 메모이제이션, DFS, DP

1. 다른 것들도 모두 파악 가능 2. 오케이 3. 비트연산 4. 메모이제이션 5. 따로 따로 공부를 진행해 볼 필요가 있음 6. DP 7. 예제를 만들어야 하는가? 8. 문제이해는 쉬움 9. 비트연산 쉽게 연습

#include <stdio.h> //비트연산 + 메모이제이션 int x[10], y[10]; int g[10][10]; int d[10][1 << 10]; // d[i][j] : j를 마지막 장소로 i고객을 방문할 때 최소 거리 int aabs(int a) { return a < 0 ? -a : a; } int main() { freopen("input.txt", "r", stdin); int tc; scanf("%d", &tc); for (int cc = 1; cc <= tc; cc++) { int N; int cx, cy; int hx, hy; scanf("%d", &N); scanf("%d%d%d%d", &cx, &cy, &hx, &hy); for (int i = 0; i < N; i++) scanf("%d%d", &x[i], &y[i]); for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) { g[i][j] = g[j][i] = aabs(x[i] - x[j]) + aabs(y[i] - y[j]); } int m = 1 << N; for (int i = 0; i < N; i++) for (int j = 0; j < m; j++) d[i][j] = 8192; for (int i = 0; i < N; ++i) d[i][(1 << i)] = aabs(x[i] - cx) + aabs(y[i] - cy); //i만 방문했으므로 회사에서 바로온것 for (int j = 1; j < m; ++j) //만들어진 조합 { for (int i = 0; i < N; ++i) //이전 마지막 장소 { if (j&(1 << i)) //이전 장소가 조합에 포함되있어야함 { for (int k = 0; k < N; ++k) //추가로 방문할 장소 탐색 { int l = j | (1 << k); //j에 k번호를 추가시킴 if (j == l) continue; //if (d[i][j] == 0) { continue; } if (d[k][l] > d[i][j] + g[i][k]) d[k][l] = d[i][j] + g[i][k]; //k를 마지막으로 방문하고 l조합을 만드는 값을 갱신s } } } } int res = 987654321; int j = m - 1; for (int i = 0; i < N; i++) { if (res > d[i][j] + aabs(x[i] - hx) + aabs(y[i] - hy)) res = d[i][j] + +aabs(x[i] - hx) + aabs(y[i] - hy); } printf("#%d %d\n", cc, res); } }