dt43111   4년 전

R1, R2, B1, B2 로 점 4개를 잡았다고 하면

R1 -> R2의 최저 찾은 후 길에 못가게 맵에 경로를 flag값으로 두고 B1 -> B2의 최저를 찾고

맵클리어 후

B1 -> B2의 최저 찾은 후 길에 못가게 맵에 경로를 flag값으로 두고 R1 -> R2의 최저를 찾고

(선 R1 -> R2 + 후 B1 -> B2) 와 (선 B1 -> B2 + 후 R1 -> R2) 둘을 비교하여 적은값을 출력시키되 못갈경우를 처리해줬습니다

선 찾는과정 후 찾는과정 의 조합을

선 DFS 후 DFS = 시간초과

선 DFS 후 BFS = 시간초과

생각을 더 해보고

어차피 최저가 ㄱ 혹은 ㄴ 모양으로 완성될수도 있기 때문에 DFS대신 ㄱ 혹은 ㄴ 으로 가면서 다른점이있는지 예외를 체크하여 다른 점 없을경우 ㄱ 혹은 ㄴ 경로로 배치하고 예외가 있을경우 위처럼 DFS를 돌리는형식으로  구현하였습니다

= 시간초과가 뜹니다


어떻게 가야할까요 방법좀 가르쳐주시면 감사하겠습니다


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