1. bfs 를 해서 계속 돌아가는데, 섬을 가지고 돌아다닙니다. 그런데 만약에 섬을 가지고 돌아다니다가, 이게 하도 돌아서 섬이 커지면 d_map 에 적용되지 않도록 합니다. 2. 그것을 위해서 처음에 d_map 은 엄청 큰 수로 넣어주고, 가지고 다니는 섬끼리 비교를 하도록 해서 작은 섬만 남도록 합니다. 3. 그래서 이것이 끝점까지 도달하면 끝. 가지치기가 그렇게 많이 필요없는 이유는 섬이 조금만 방황해도 엄청 숫자가 커지기 떄문에, 빠르게 감소할 것 입니다. |
/* 1330 시작해서 풀어보도록 하겠습니다. 보급로 문제 dp 로 풀어보도록 하겠습니다. */ #include <iostream> #include <algorithm> #include <string> #include <queue> #define SIZE 104 // 102 using namespace std; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int d_map[SIZE][SIZE]; int minVal = 2123456789; int N; string str; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int ans; struct point { int x, y, sum; }; queue<point> que; int x, y, nx, ny, sum; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { cin >> str; for (int j = 0; j < N; j++) { map[i][j] = str[j] - '0'; d_map[i][j] = 2123456789; } } } void init() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d_map[i][j] = 2123456789; } } } void bfs() { while (!que.empty()) { x = que.front().x; y = que.front().y; sum = que.front().sum; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < N) { if (sum + map[nx][ny] < d_map[nx][ny]) { d_map[nx][ny] = min(d_map[nx][ny], sum + map[nx][ny]); que.push({ nx,ny, sum + map[nx][ny] }); } } } } } void solve() { que.push({ 0,0,map[0][0] }); d_map[0][0] = map[0][0]; bfs(); } int main() {
int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << "#" << tc << " " << d_map[N-1][N-1] << endl; init(); } return 0; } |