웹마스터 팁
[OsE=] 최단 거리...
2002.03.02 22:42
PHP보다는 알고리즘에 가깝죠...
일단
왼쪽 하단에서 오른쪽 상단으로 이동할때의 최단거리는
오른쪽 위쪽으로만 움직여서만 가면 최단거리입니다.
무조건말이죠 -0- 그건 여러분들이 일일이 해보거나
수학적으로 계산해보아도 저 명제는 성립합니다.
여기서 문자 실험을해야하는건가?
-_-좀 쉬운방법으로 풀이를 해보죠
-map-(참고로 이건 2차원변수)
00004
00000
02200
00222
30000
여기서 시작점은 3, 도착점은 4라고하고 2는 장애물이라고 합시다
그렇다면 일단... -_-3에서 갈수있는 길을 2가지길입니다.
그리고 모두 위, 오른쪽입니다.
그렇다면,
-map-
00004
00000
02200
10222
31000
지나간 자리는 1로 표시를 해줍니다.
그리고 3차원배열에
-maps[1]-(이건 3차원배열입니다
00000
00000
00000
00000
11000
-maps[2]-(이건 3차원배열입니다
00000
00000
00000
10000
10000
그리고 다시
-map-
00004
00000
02200
10222
31000 에서 또 모든곳을 갈수있네요 2경로에서 다~(오른쪽 위로만 가면 최단경로니까)
그럼
-maps[3]-(이건 3차원배열입니다
00000
00000
00000
00000
11100
-maps[4]-(이건 3차원배열입니다
00000
00000
00000
0!000
11000
-maps[5]-(이건 3차원배열입니다
00000
00000
00000
11000
10000
-maps[6]-(이건 3차원배열입니다
00000
00000
10000
10000
10000
그리고 다시
-map-
00004
00000
12200
11222
31100
아. 그리고 이제 갈수있는 길은 2개밖에없네요.. 하나는 오른쪽으로만 다른건 위로 밖에만... 그러면
-maps[7]-(이건 3차원배열입니다
00000
10000
10000
10000
10000
-maps[8]-(이건 3차원배열입니다
00000
00000
10000
10000
11110
이런식으로 -_-;; 하는겁니다.. -_-;; 제가 더이상 시간 때문에 끝까지 못하겠고요
생각을 해보세요^-^
일단
왼쪽 하단에서 오른쪽 상단으로 이동할때의 최단거리는
오른쪽 위쪽으로만 움직여서만 가면 최단거리입니다.
무조건말이죠 -0- 그건 여러분들이 일일이 해보거나
수학적으로 계산해보아도 저 명제는 성립합니다.
여기서 문자 실험을해야하는건가?
-_-좀 쉬운방법으로 풀이를 해보죠
-map-(참고로 이건 2차원변수)
00004
00000
02200
00222
30000
여기서 시작점은 3, 도착점은 4라고하고 2는 장애물이라고 합시다
그렇다면 일단... -_-3에서 갈수있는 길을 2가지길입니다.
그리고 모두 위, 오른쪽입니다.
그렇다면,
-map-
00004
00000
02200
10222
31000
지나간 자리는 1로 표시를 해줍니다.
그리고 3차원배열에
-maps[1]-(이건 3차원배열입니다
00000
00000
00000
00000
11000
-maps[2]-(이건 3차원배열입니다
00000
00000
00000
10000
10000
그리고 다시
-map-
00004
00000
02200
10222
31000 에서 또 모든곳을 갈수있네요 2경로에서 다~(오른쪽 위로만 가면 최단경로니까)
그럼
-maps[3]-(이건 3차원배열입니다
00000
00000
00000
00000
11100
-maps[4]-(이건 3차원배열입니다
00000
00000
00000
0!000
11000
-maps[5]-(이건 3차원배열입니다
00000
00000
00000
11000
10000
-maps[6]-(이건 3차원배열입니다
00000
00000
10000
10000
10000
그리고 다시
-map-
00004
00000
12200
11222
31100
아. 그리고 이제 갈수있는 길은 2개밖에없네요.. 하나는 오른쪽으로만 다른건 위로 밖에만... 그러면
-maps[7]-(이건 3차원배열입니다
00000
10000
10000
10000
10000
-maps[8]-(이건 3차원배열입니다
00000
00000
10000
10000
11110
이런식으로 -_-;; 하는겁니다.. -_-;; 제가 더이상 시간 때문에 끝까지 못하겠고요
생각을 해보세요^-^
댓글 6
-
제니
2002.03.02 23:32
-
박규철
2002.03.05 13:14
긁적 긁적 이게 무슨 말씀이신지 도통...
긁적 긁적... -
권성태
2002.03.30 20:54
다익스트라 돌리면 끝인데 -
토끼군
2002.06.05 21:02
Dijkstra나 Floyd 등의 알고리즘으로 구현할 수 있습니다;; 설명은 귀찮아서 못하고;;;; 대충 찾아보세요;;;;;;;; (헉;;;;;;;;;;;;;;;; 한마디 할때마다 땀이 두배로;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;)
권성태 // 너냐? -_-; 자세한 설명좀 써놓으면 좋으련만; -
김승환
2002.11.30 20:38
플로이드는 일반적으로 모든 경로의 최단경로를 구하는 동적계획법의 일종입니다.
예를 들자면 A,B,C,D,E의 5개의 노드가 있습니다.
A에서 E로 가는데 B를 거쳐서 A-B-E로 가거나,
C를 거쳐서 A-C-E로 가거나 A-D-E로 가거나 이런식으로 계속 거쳐가는것을 생각해가면서 최단경로를 만듭니다...
다이크스트라는 제가 별로 안써서 까먹었네요;;; 그리디인데... -
김승환
2002.11.30 20:52
아 생각났습니다;;;; 다이크스트라....(다이크스트라 알고리즘을 만든 다이크스트라가 9월경에 돌아가셨습니다...애도를.....)
역시 A,B,C,D,E 5개의 노드가 있고 A에서 E로 간다고 생각합니다.
일단 A에서 갈수 있는 가장 가까운 노드를 선택해서(예를 들어 B)
A에서 앞에 선택한 B를 거쳐서 다른 노드들(C,D,E)로 가는것과 A에서 곧바로 다른 노드들(C,D,E)과 가는것을 비교, 갱신합니다.
즉 A-B-C로 가는것과 A-C로 가는것 A-B-D와 A-B를....이런 순으로 쭉 비교하죠.
그다음에 다시 이미 지나온 노드들(A와 B겠죠)를 제외한 다른 노드들중에서 A와의 거리가 가장 짧은 노드를 선택(예를 들어 D..)해서 이 노드를 거쳐서 이미 지나오지 않은 노드들을 가는 거리를 계산해서 비교, 갱신 해나갑니다...
A에서 C로 가는데 A-B-C로 가는것이 최단이었다면 위에 위에 과정으로 인해
A노드에서 C노드로 가는 경로는
A-C -> A-B-C 로 수정이 되겠죠. 여기서 다시 A-B-D-C와 기존에 갱신돼있던 A-B-C의 경로를 비교해서 다시 갱신하고.....합니다;;;;
지금까지 제가 설명하면 아무도 못 알아들었지만 혹시나 해서 참고 삼아 올려봅니다...
| 제목 | 글쓴이 | 날짜 |
|---|---|---|
| [OsE=] 최단 거리... [6] | OsE= | 2002.03.02 |
| [OsE=] IF 대신... [6] | OsE= | 2002.03.02 |
| [Yuki-H.] 이미지 크기가 일정 픽셀 이상이면 축소하여... [8] | Yuki-H. | 2002.03.04 |
| 많은것을 파일하나로 처리하잣!! [5] | 실버 | 2002.03.05 |
| 2번째~~!! DATE값 받아놓기 &상대방 아이피 알아내기~ [7] | 실버 | 2002.03.07 |
| 요일을 한글로 표시 [5] | 페리스 | 2002.03.10 |
| 반복문을 한번만 사용한 구구단 [2] | 페리스 | 2002.03.10 |
| php를 리눅스쉘상 에서도 사용하자? [5] | 실버 | 2002.03.10 |
| 유용한 함수 - array_reverse | 리들 | 2002.03.10 |
| 가변적 변수 할당하는 방법 (t1=1; t2=2; t=t.rand(1,2);) [1] | 차카게살자 | 2002.03.11 |
| [추천 팁] index key 값을 갖는array에서 value에 의한 key값 반환 [1] | 차카게살자 | 2002.03.11 |
| include를 이용한 다음넷 홈페이지 꾸미기1 [10] | ZipShin | 2002.03.12 |
include를 이용한 다음넷 홈페이지 꾸미기2(그림 첨부)
[4]
 | ZipShin | 2002.03.12 |
| TheMics의 예제와 함께하는 PHP기초(上) [1] | TheMics | 2002.03.14 |
| [씽크식 PHP] 초심자들이 많이 겪는 실수.. [7] | [ζ]씽크 | 2002.03.16 |
| echo 문 대신... [5] | TryZ | 2002.03.17 |
| [추천 팁] 방문자의 os와 browser체크 함수.... [3] | navyism | 2002.03.18 |
| [추천 팁] setcookie()사용시 header어쩌구 하는 에러날때.... [1] | 하얀바다 | 2002.03.19 |
| [추천 팁] [씽크식 PHP] PHP에대해 아무 지식이 없는 사람이 오해하는것. [3] | [ζ]씽크 | 2002.03.23 |
| [씽크식 PHP] 글자 하나씩 때어놓기.. (한글 자르기 포함) [1] | John Sync. | 2002.03.26 |
수고 하셧습니당 :)