이건...조만간 틀린 답안이 될 것이다.
현재는 맞았지만!!!왜냐하면 테케가 빈약했기 떄문이다!!!!!
나는 가능한 모든 벽을 하나씩 부순 후, 각각에 대하여 BFS(백트랙킹)를 해주었다. 그리고 이 중에서 최솟값을 출력해주었는데..
이렇게 하면 시간 복잡도가 맵의 크기를 1000으로 두면 1000*1000*1000*1000이다.!!!
결론은 틀린 답안~이지만 일단 올림.
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 | #include <stdio.h> #include <string.h> #define MAX 999999 int M, N, MIN; int MAP[1111][1111]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,-1,1 }; void BACK(int y, int x, int len) { if (MAP[y][x] == 1 || len > MIN) return; if (y == M && x == N) { if (len < MIN) MIN = len; return; } MAP[y][x] = 1; for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx > N || yy > M || xx <= 0 || yy <= 0) continue; if (MAP[yy][xx] == 0) { BACK(yy, xx, len + 1); } } MAP[y][x] = 0; return; } int main() { scanf("%d %d", &M, &N); for (int i = 0; i <= 1011; i++) { for (int j = 0; j <= 1011; j++) { MAP[i][j] = 1; } } for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { scanf("%1d", &MAP[i][j]); } } MIN = MAX; BACK(1,1,1);//벽 부수지 않고 최단경로 찾기 for (int i = 1; i <= M; i++)//벽 하나씩 부숴가면서 최단경로 찾기 { for (int j = 1; j <= N; j++) { if (MAP[i][j] == 0 || (i == 1 && j == 1)) continue; if ((MAP[i + 1][j] == 1 || i + 1 > M) && (MAP[i][j + 1] == 1 || j + 1 > N) && (MAP[i - 1][j] == 1 || i - 1 < 1) && (MAP[i][j - 1] == 1 || j - 1 < 1))//0으로 바꾸었는데, 사방에 1이면 노 필요~ { continue; } MAP[i][j] = 0; BACK(1, 1, 1); MAP[i][j] = 1; } } if (MIN == MAX) { printf("-1\n"); return; } printf("%d\n", MIN); return 0; } | cs |
'SW 업무 관련 > 백준' 카테고리의 다른 글
[C언어] 2015 오목. (0) | 2018.08.21 |
---|---|
[C언어] 7562. 나이트의 이동 (0) | 2018.08.14 |
[C언어] 2667. 단지 번호붙이기 (0) | 2018.08.12 |
[C언어] 1012. 유기농배추 (0) | 2018.08.12 |
[BAEKJOON] 2606_바이러스 (0) | 2018.06.06 |