본문 바로가기

Algorithm/BOJ172

[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.
[BOJ]5014번: 스타트링크 문제: https://www.acmicpc.net/problem/5014 BFS 문제입니다. 매 상태는 +U, -D로 두 가지로 분기됩니다. 낚일만한 요소는 F층이 최상단층이라는 것만 안 빼먹으시면 무난히 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ5014.java 2020. 8. 13.
[BOJ]1039번: 교환 문제: https://www.acmicpc.net/problem/1039 BFS 문제입니다. 예외조건 때문에 많이 틀렸네요. 세 가지 주의점이 있습니다. 1. 바뀐 후의 숫자가 0으로 시작하면 안됩니다. 2. 10,20,30처럼 두 자리수이면서 0으로 끝나는 숫자는 Swap하면 안됩니다. (단, 100,1000,10000 같은 숫자들은 괜찮습니다. 0 끼리 바꾸면 되니까요) 3. 총 K번 Swap 회차만큼 Swap을 할텐데, 각 회차가 될 때 마다 방문배열을 초기화해줘야 합니다. 무슨 말이냐면 이전에 나왔던 숫자가 나중에 나와도 됩니다. 이를 위해서 저는 매 루프를 while (!q.empty()) 가 아니라 while (q.size()--) 만큼만 돌았습니다. 코드: https://github.com/.. 2020. 8. 13.

티스토리툴바