1211. [S/W 문제해결 기본] 2일차 - Ladder2(D4)

각각의 시작점에서 출발하여 각각의 도착점까지의 길이가 가장 짧은 시작점을 찾는 문제이다.

시작점부터 하나씩 길이를 계산하며, 시간을 줄이기위해, 중간에 계산된 길이가 이미 계산된 최솟값보다 커지면 다음 시작점을 탐색한다.

#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;
}