dth04019   7년 전

조금 지저분하게 짜긴 했는데 제가 빼먹은 부분이라던가 틀린 케이스 좀 찾아주세여 ㅜㅜ

methylene   7년 전

각 지점사이의 거리를 플로이드로 갱신시키는 부분(경유지와의 거리의 합으로 갱신 시키는 것)부터 잘못 되었구요
집과 각 편의점 사이의 거리를 정렬시켜 각 지점 사이의 거리를 구하는 것도 잘못 되었습니다.
happy  인 경우에도 지나가지 않는 지점, 그러니까 혼자 멀리 떨어진 편의점이 있을 수가 있는데 모든 지점과 바로전 지점 사이의 거리를 따지면
sad라고 잘못 판단을 내릴 수 있죠.
플로이드는 1000미터 이내인가 아닌가를 판별하는 1, 0만을 집어넣는 배열을 따로 만드는 것이 편합니다.
그것이 싫으시다면 (메모리 문제도 있고 이중 포문을 한번 더 돌려야 하는 것도 있고)

for (k = 1; k <= N + 2; ++k) {
            for (i = 1; i <= N + 2; ++i) {
                for (j = 1; j <= N + 2; ++j) {
                    if (siri[i][j] > max(siri[i][k], siri[k][j])) {
                        siri[i][j] = max(siri[i][k], siri[k][j]);
                    }
                }
            }
        }

이런 식으로 거리의 합이 아니라 두 거리 중 큰 값을 덧 씌우는 식으로 플로이드를 돌리면 됩니다.

(두 경우 거리 중 먼 거리를 보고 맥주를 먹으면서 가는 것이 가능한 경로인지 확인하기 위해)


methylene   7년 전

0, 1로 가능성만을 따진 배열을 추가한 경우

dth04019   7년 전

오 감사합니다 ㅎㅎㅎ

댓글을 작성하려면 로그인해야 합니다.