211105 금 Algorithms TIL

플로이드

• 문제
• 코드

파이썬

• 백준 pypy로 제출해야 풀린다
• 플로이드 워셜을 초기화 할 때 max값을 나올 수 있는 경로의 최대값 100001로 해주고 밑에 값 체크를 할 때 경로 < 100001 했는데 그러면 안된다. 왜냐하면 그렇게 되면 어떤 경로의 값이 10000이고 i->j->k 를 거쳐서 가는 방법이 있는데 그렇게 하면 경로가 10000 + 10000 되어서 20000이 되기 때문. 그래서 동빈북에서 INF라는 변수를 쓰나 보다

화성 탐사

• 동일백준문제
• 코드
• 동일백준문제코드
• 동빈북 ch17 최단경로 문제
• 동빈북에 있던 ch05 dfs/bfs 미로탈출 문제와 같다고 생각하여 그렇게 풀려고 하였으나 그것은 모든 경로가 똑같을 때 풀 수 있는 문제였다.
• 경로의 문제,(경로의 값이 모두 다른 문제는 최단경로 문제로 풀어주는 것이 맞다)

내풀이

• 난 굳이굳이 n ** 2 크기의 그래프를 만들어주었는데 동빈북은 distance 그래프 자체를 이차원 그래프로 만들었다.

동빈북풀이

• 동빈북은 나와 차이가 있다면 나는 목적지에 출발지 거리는 출발지의 값으로 했다면 동빈북은 목적지의 값으로 했다.