알고리즘
20/01/07
openingsound
2020. 1. 7. 01:04
푼 문제들
문제집: N과 M (baekjoon)
www.acmicpc.net
N과 M은 큰 문제가 없었음
치킨배달은 설계 구현 정답까지 맞았지만 쉽게 구하는 방법이 있는데 어렵게 풀었음
집과 치킨집의 거리를 구할때 bfs를 이용해 구했을 때는 시간이 72ms였지만 각 좌표의 차의 합을 바로 계산하였을 때는 0ms로 바로 풀림 지점에 장애물이 있을때나 제약이 있을경우 bfs를 해야하지만 그렇지 않을경우엔 멘헤튼거리를 이용하면됨
https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC
맨해튼 거리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 맨해튼 거리와 유클리드 거리의 비교: 빨간색, 파란색, 노란색 선은 길이가 12로 같으며, 유클리드 거리와 맨해튼 거리 양쪽 모두 가지고 있다. 유클리드 기하학의 경우 초록색 선의 길이는 6×√2 ≈ 8.48로, 선들 가운데 유일하게 길이가 가장 짧으며, 맨해튼 거리의 경우 파란색 선의 길이는 12로, 이보다 길이가 더 짧은 선은 없다. 맨해튼 거리(Manhattan distance, 혹은 택시 거리, L1 거리, 시가지
ko.wikipedia.org