플로이드 워셜로 구하는 그래프의 사이클의 길이

1956번: 운동   시작점에서 다시 시작점으로 돌아오는 사이클을 찾고자 하는데, 이때 길이 합이 가장 작은 사이클을 찾는 문제 사이클을 찾아야하나?  dfs로 돌려서 사이클 찾고 해야하나.. 생각했는데 꼭짓점이 최대 400개이기도 하고 플로이드 워셜로 i번에서 시작해서 i번으로 돌아오는 최단 거리 dp[i][i]를 구하면 될것 같다 사이클이라는게 결국 i번에서 시작해서 i번으로 돌아오는거니까 일반적인 경우와 다르게 dp[i][i] = 0으로 하지말고 dp[i][i] = INF로 초기화함  꼭짓점이 1~V번이니까 1번부터 V번 돌아야하는거 실수하지말고 마지막에 dp[i][i]돌아서 최솟값을 찾으면 그것이 길이가 최소인 사이클의 길이 answer = INF로 변화없으면 사이클이 없는거고 from sys i..

• format_list_bulleted 최단거리 알고리즘
• · 2025. 1. 5.
• textsms

비전공자도 이해할 수 있는 AI지식 -내비게이션이 최단거리를 찾는 방법-

1. 다익스트라, 최단거리를 탐색하게 해주다 강남역의 교통 체증 여부를 예측했으니, 이제 내비게이션으로 최적의 경로를 찾을 일만 남았습니다. "강남역으로 안내해줘"라는 명령에 따라 내비게이션은 과연 어떻게 강남역까지 최적의 경로를 찾을 수 있을까요? 최단 경로를 찾는 알고리즘 중에서 가장 유명한 것은 아마 다익스트라 알고리즘(Dijkstra's Algorithm)일 것입니다. 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 대학원생이던 1956년 여자친구와 함께 커피숍에 갔다가 20분만에 고안해서 만든 알고리즘으로 알려져 있습니다. 커피숍에서 냅킨에 적을 수 있을 만큼, 단순한 법칙이 가장 뛰어나다는 오컴의 면도날을 증명하는 대표적인 알고리즘이기도 합니다. 물론 당시에 그는 이렇게 단순한 경로 계획 알고..

• format_list_bulleted 비전공자도 이해할 수 있는 AI지식
• · 2023. 1. 5.
• textsms

사각맵에서 가장 빨리 목적지로 도달하는 최단 경로 찾는 방법

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5*5 크기의 맵에, 당신의 캐릭터가 (행:1, 열:1) 위..

• format_list_bulleted 알고리즘 일반
• · 2022. 5. 3.
• textsms