2146번 - 다리 만들기
항상 제가 푸는 문제는 예제만 맞고 서버에 올리면 틀리는건지 모르겠네요.
제가 생각한 알고리즘은 다음과 같습니다.
1. DFS하면서 섬에 번호를 매긴다.
2. 각 섬 번호에 해당하는 좌표중에서 해안가에 위치한 좌표만 리스트에 담는다.
3. 섬들간에 해안선 좌표들간에 가장 최소인 값을 찾는다.
|x1 - x2| + |y1 - x2| 공식 이용
3. 최소값에서 -1 을 해준다. 왜냐만 다리만 연결해주면 되므로..
댓글을 작성하려면 로그인해야 합니다.
filot 7년 전
항상 제가 푸는 문제는 예제만 맞고 서버에 올리면 틀리는건지 모르겠네요.
제가 생각한 알고리즘은 다음과 같습니다.
1. DFS하면서 섬에 번호를 매긴다.
2. 각 섬 번호에 해당하는 좌표중에서 해안가에 위치한 좌표만 리스트에 담는다.
3. 섬들간에 해안선 좌표들간에 가장 최소인 값을 찾는다.
|x1 - x2| + |y1 - x2| 공식 이용
3. 최소값에서 -1 을 해준다. 왜냐만 다리만 연결해주면 되므로..