문제풀이 (12) 썸네일형 리스트형 백준 1781번(JAVA) 처음엔 이 문제를 그리디 알고리즘에 넣어야 하나, 우선순위 큐 카테고리로 넣어야 하나 고민했다. 근데 뭐 큰 의미없는 거 같아서 걍 그리디 알고리즘에 넣는다. 처음에는 그냥 단순히 마감시간이 적은것이 큰 우선순위를 갖도록, 그리고 마감시간이 같다면 컵라면 개수 많이주는걸 우선순위가 크게 우선순위큐에 넣었다. 예제는 잘 통과했는데 바로 틀렸다. 이유는 만약 문제가4개라 할떄 문제번호 1 2 3 4 데드라인 1 1 2 2 컵라면 개수 10 20 100 100 이런 경우에서 자연스럽게 데드라인 1중 컵라면개수가 더 많은 20을 택한다. 그리고 흘러간시간을++해준다. 그 후, 데드라인 2중에서 하나를 택해서 100을 골라서 총 컵라면개수는 120개가 된다. 하지만 사실 처음에 3번을 풀고 그 다음에 4번을 풀면.. 백준 10282번(JAVA) 기본적인 다익스트라 문제이지만 원하는 값은 다르다. 정점의 개수가 주어지고 출발점에서 시작해서 도달 할 수 있는정점은 몇개인지(시작점 포함), 그리고 도달 할 수있는 정점중 가장 거리가 먼것은 몇인지 출력하면된다. 간단하게 일반적인 다익스트라를 실시한다. 일반적인 다익스트라에 관한 문제는 아래에 링크를 걸어두겠다. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 단순하게 시작점에서 해당 정점까지의 거리를 나타내.. 백준 11779번(JAVA) 이번 문제는 다익스트라 알고리즘에다가 되추적까지 해줘야 하는 문제다. 문제의 조건에는 안나와있지만 정점은 1번부터n번이다. 기본적으로 다익스트라와 동일하다. 단, 되추적을 위해 int[] before 배열을 선언한다 예를들어 최단거리 경로가 1번에서 3번으로 가기위한 최단 경로가 1->2->3일경우 before[3]=2, before[2]=1을 집어넣는다. 되추적은 일단 index를 end로 잡는다 그리고 루프를 돌면서 index를 스택에 넣고 index=before[index] 실시하고 count값을 증가시켜준다. 만약 index가 start가면 루프를 깬다. count값을 출력하고 stack이 빌 때까지 계속 출력해주면 된다. stack에는 처음에 index를 집어넣으면 end가 들어가고 마지막에는 .. 백준 1261번(JAVA) 다익스트라를 응용하는 문제이다. BFS와 다익스트라를 모두 다룰줄 안다면 손쉽게 풀 수 있다. 기본 다익스트라를 모를 경우 아래 링크에서 참고하도록 하자. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 일반 다익스트라와 다른점을 꼽자면 굳이 연결정보를 안알려준다는 것이다. 나는 단순하게 생각했다. 현재정점의 위,아래,오른쪽,왼쪽은 모두 연결되어있으며 만약 벽이 있다면 가중치가 1,벽이 없다면 가중치가 0.물론.. 이전 1 2 다음