각각의 시작점에서 출발하여 각각의 도착점까지의 길이가 가장 짧은 시작점을 찾는 문제이다.
시작점부터 하나씩 길이를 계산하며, 시간을 줄이기위해, 중간에 계산된 길이가 이미 계산된 최솟값보다 커지면 다음 시작점을 탐색한다.
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 | #include <stdio.h> int main(void) { for (int z = 1; z <= 10; z++) { int n; scanf("%d", &n); int map[102][102] = { { 0, }, }; int x, y; for (int i = 1; i <= 100; i++) { for (int j = 1; j <= 100; j++) { scanf("%d", &map[i][j]); } } int ans = 0; int min = 2e9; for (int j = 1; j <= 100; j++) { if (map[1][j] == 1) {//시작점 y = j; int cnt = 0; for (int i = 1; i <= 100; i++) { cnt++; if (map[i][y + 1] == 1) { while (true) { y++; cnt++; if (map[i][y + 1] != 1) { break; } } } else if (map[i][y - 1] == 1) { while (true) { y--; cnt++; if (map[i][y - 1] != 1) { break; } } } if (cnt > min) { break; } } if (cnt <= min) { ans = j - 1; min = cnt; } } } printf("#%d %d\n", z, ans); } return 0; } | cs |