전체 글 (88) 썸네일형 리스트형 백준 20010 <악덕 영주 혜유> 최소 스패닝 트리를 찾고 그 지점에서 가장 긴 거리의 합을 계산하는 문제이다. 문제 풀이 0번 마을부터 시작해서 프림 알고리즘을 구성하면서 연결된 지점을 새로운 arraylist에 넣어준다. 0번 마을에서부터 dfs를 하면서 가장 길게 이어진 합을 갱신해준다. 최소 스패닝을 구하게 되면 그림과 같이 빨간색 선들로 이뤄진 길이가 된다. 그중 가장 긴 길이는 0번 집에서 6번 집까지의 거리를 구하는 것이다. 즉 dfs를 하면서 가장 긴 길이를 매번 update 해주는 것이다. 연결되어 있는 집들과 그사이의 거리를 담을 div 클래스를 생성한다. 최소 스패닝 트리를 구성하기위해 kruskal 또는 prim 알고리즘을 사용하면 되는데 나는 여기서 prim알고리즘을 사용했다. 마을과 마을 중 가장 먼 거리를 구하.. 백준 20007 <떡 돌리기> 성현이 집에서 모든 집의 가장 가까운 거리를 찾는 것이 필요한 문제이다. 즉 다익스트라 알고리즘을 사용하는 문제이다. 다익스트라 알고리즘을 사용하면서 마을마다 가장 가까운 거리를 기억하고 그 정보를 이용해 며칠이 걸리는지를 푸는 문제이다. 문제 해결 다익스트라 알고리즘을 이용해서 각각의 마을의 가까운 거리를 큐에 담아준다. 큐에서 꺼내면서 현재 이동할수 있는 거리보다 작으면 하루를 더해준다. 예외사항의 경우는 성현이 집에서 모든 집을 방문할 수 없을 때와 성현이가 왕복할 수 있는 거리보다 거리가 더 멀 때 -1을 출력한다. 문제를 잘읽자. 다익스트라 알고리즘이다. 이를 통해서 우선순위 큐로 인해 거리가 작은 순서대로 정렬되기 때문에 방문하지 않았을 경우 q에 담으면 거리가 가까운 순으로 정렬된다. 예외사.. 백준 2636 <치즈> 기본 완전 탐색으로 풀어도 통과가 되는 골드 5 수준의 문제이다. 치즈가 전체 꽉 차 있더라도 치즈가 녹는 시간은 가장 n과 m 중 큰 수의 1/2 그리고 접체 맵의 크기만큼 n*m이므로 n*m*(최대)/2 이므로 50만이 최대이기때문에 시간 초과는 날 수 없다. 그러나 맵 크기만큼인 최대인 10000번 으로 끝내는 방법으로 구성했다. 풀이 방법 0,0 지점은 치즈 가 존재하지 않기 때문에 bfs를 진행하며 visit처리를 하고 1 즉 치즈가 위치 한 곳이면 list라는 큐에 넣어 주었다. 가장 끝점의 치즈가 list에 담겨있을 것이고 여기서 Queue를 제거하면서 방문하지 않은 1이면 다시넣어주고 방문하지 않은 0이면 즉 --> 구멍이기 때문에 bfs를 수행해 list에 담아 주었다. list가 빌때까.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 30 다음
