목록전체 글 (35)
알고리즘 공부방
https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 문제 풀이 이 문제를 보고 바로 떠올린 것은 폴로이드 워샬 알고리즘이었다. 하지만, 폴로이드 워샬을 썼을 때 첫번째 경유지를 어떻게 처리해야할지 고민하고 있었는데, 이 문제의 범위를 보니 시간 복잡도 O(E log V) 다익스트라 알고리즘으로 풀릴거라 생각이 들었다. 먼저 Node 클래스를 정의해 다음 정점과 가중치, 처음으로 들렸던 정점을 정의해주었다. static class Node implements..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제풀이 방법 먼저 다익스트라 알고리즘을 공부하고 싶다면 아래의 문제를 한번 풀어보는 것을 추천한다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 먼저 나는 이 문제를 보고 BFS방식에서 큐에 벽을 부쉈는지 확인해주는 변수를 넣어주면 되는 문제인 줄 알았다. 하지만 틀렸다. 여기서 내가 생각하지 못했던 것이 벽을 부수고 진행했던 경로와 벽을 부수지 않고 진행한 경로가 겹칠 수 있는 구간이 있을 수 있다는 것을 놓쳤었다. 그렇기에 이 문제를 해결하기 위해선 평소에 쓰던 visted 변수를 2개를 만들어서 벽..