[PS]맞왜틀 시리즈6 범위

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다.

우리는 그럴때 이렇게 말한다.

범위? 무슨 범위?

틀리기 쉬운 범위는 다음과 같다.

 

1) for, while 과 같은 반복문 횟수, 반복문 시작, 종료 위치

C/C++에서 사용하는 배열은 0부터 시작한다. 그런데 보통 알고리즘 문제에서 주어지는 번호가 1번부터 시작한다.

입력받을때는 배열의 1번부터 N번까지 입력을 받는데

반복문을 돌릴때 0번부터 N-1 까지 접근하는 경우가 많다. 아래 예시를 보자

for(int i = 0; i < N; ++i)
    arr[i];

https://www.acmicpc.net/problem/11404

11404번: 플로이드

전체 코드

//문제: https://www.acmicpc.net/problem/11404
#include <stdio.h>
void floydwarshall(int d[][101], int N) {
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
            }
        }
}
 
int main() {
    int d[101][101];
    const int INF = 90000000;
    for (int i = 0; i < 101; ++i)
        for (int j = 0; j < 101; ++j)
            if (i == j)
                d[i][j] = 0;
        else
                d[i][j] = INF;
    //Input
    int N, M;
    scanf("%d", &N);
    scanf("%d", &M);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (d[a][b] == INF)
            d[a][b] = c;
        else
        {
            if(d[a][b] > c)
                d[a][b] = c;
        }
    }
    //----------solution
    floydwarshall(d, N);
    //Output
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (d[i][j] == INF)
                printf("0 ");
            else
                printf("%d ", d[i][j]);
        }
        printf("\n");
    }
}