백준 알고리즘44 [BOJ]1525번: 퍼즐 https://www.acmicpc.net/problem/1525 BFS 문제입니다. 문제를 쉽게 만들 수 있는 방법은 '0'을 '9'로 치환해서 풀면 됩니다. 그러면 맨 앞자리에 0이 오는 경우도 int 자료형으로 처리할 수 있습니다. 정답 숫자는 123456789가 되겠네요. swap을 통해 좌표를 움직여주는 방법은 1차원으로 움직이든, 2차원으로 움직이든 상관없습니다. (저는 1차원 배열 형태로 해결했습니다.) set를 통해 방문했던 상태를 저장하면 해결할 수 있습니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1525.cc 2020. 8. 17. [BOJ]10217번: KCM Travel https://www.acmicpc.net/problem/10217 바킹독님 풀이를 통해서 해결했습니다. (https://blog.encrypted.gg/164) DP[i][j]: "1번 노드부터 i번 노드까지 비용 j를 써서 갈 때의 최소 시간"으로 상태를 정의합니다. 예외 조건은 j 값이 M을 초과하면 예외입니다. (continue) 이렇게 상태를 정의하고 1번 노드부터 다익스트라를 돌리면, "비용 M 이하" 조건을 만족하는 경로 중에서 가장 먼저 N번 노드에 도착하는 경로가 최소 시간을 만족하는 정답입니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ10217.cc 2020. 8. 17. [BOJ]16681번: 등산 문제: https://www.acmicpc.net/problem/16681 hororo님 풀이를 참고하여 문제를 해결하였습니다. (https://hororolol.tistory.com/3) 출발점 1과 도착점 N을 각 각 출발점으로 두 개의 다익스트라를 돌려봅니다. 첫 번째 다익스트라. 1 => 나머지 노드 두 번째 다익스트라. N => 나머지 1 => 나머지 노드의 경로는 계속 높이가 상승해야 하므로 높이가 상승하는 방향으로 다익스트라를 돌립니다. N => 나머지 노드로의 경로는 내려올 때의 문제 조건을 반대로 해석하면 이 역시 높이가 상승하는 방향입니다. 이렇게 두 개를 돌리고 이 두 정보를 활용하여 최댓값을 구하면 됩니다. for (int K = 1; K < N-1; ++K) { //max({출발점.. 2020. 8. 14. [BOJ]3055번: 탈출 문제: https://www.acmicpc.net/problem/3055 BFS 문제입니다. 아래 두 가지 조건에 맞춰서 BFS를 구현하면 됩니다. 1. 물과 고슴도치가 동시에 이동해야 하니 BFS 매 루프는 큐 사이즈 만큼만 돕니다. 2. 동시에 이동하는 과정에서 물이 고슴도치보다 우선순위가 높으니 물이 큐에 먼저 들어가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ3055.java 2020. 8. 14. 이전 1 ··· 4 5 6 7 8 9 10 11 다음
