알고리즘/BOJ 썸네일형 리스트형 6593번 6593번 - 상범 빌딩 가중치가 1로 똑같고, 최단 거리를 구하는 문제이기 때문에 BFS를 사용하였다. 대신 지금까지 풀어왔던, 1,2차원이 아닌 3차원 배열을 이용해서 최단거리를 구하였다. 풀면서 실수 했던 부분은, 좌표에서 이동할 때 map[nz][nx][ny]!='.' 이렇게 점일때 이동하는 걸로 해서, 마지막 출구인 E 값에 자꾸 도달하지 못해서 trapped 가 되었다. map[nz][nx][ny]!='#' 이런식으로 바꿔서 풀 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576.. 더보기 4485번 4485번 - 녹색 옷 입은 애가 젤다지? 이 문제는 다익스트라 알고리즘을 이용해서 풀 수 있다. (0,0)에서 (n-1,n-1) 까지의 최단거리를 구하면 되고, 주어진 값들을 가중치라고 생각하고 풀면 되기 때문이다. 근데 내가 실수했던 점은 priority queue 를 이용해서 다익스트라를 풀 때, 처음 정점의 dist는 0 으로, 나머지 정점은 INF 로 놓고 풀게 된다. 그런데 이 문제에서는 처음에 정점의 dist 값이 0 이 아닌 값으로 주어질 수 있다. 그리고 priority queue 에서는 가장 작은 값을 구하기 위해 , dist 에 집어넣을 때 -1 을 곱해서 집어 넣는다. 즉, 처음 정점을 0 으로 했을 때, 문제가 없지만 다른 수를 넣을 경우 부호가 바뀌어 문제가 발생하게 된다. 그래.. 더보기 1261번 1261번 - 알고스팟 처음에는 너무 단순하게, 다른 많은 문제들에서 처럼 map 에서의 이동하는데 가중치가 없다고 생각해서, BFS로 풀 수 있지 않을까 했지만.. 벽을 최소한으로 뚫고 가야 하기 때문에, 벽이 막혀있을 때와 막혀있지 않을 때 가중치를 줘서 풀어야 했다. 즉 움직일 때, 최소한 벽을 뚫지 않아도 되는 쪽으로 움직이는게 좋다는 뜻이었다. 따라서 벽을 파야할때는 간선의 가중치를 1로, 그냥 움직일 수 있을 때는 0으로 두고 (즉 그냥 입력값을 그대로 사용) 다익스트라 알고리즘으로 마지막까지의 값을 구했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565.. 더보기 1238번 1238번 - 파티 처음에 플로이드 알고리즘으로 풀려고 했으나, 시간제한이 넘어갈 것 같아서.. (근데 플로이드 시간 통과된다..) priority queue 를 이용한 다익스트라 알고리즘을 써서 문제를 풀었다. X 를 시작점으로 다익스트라를 한번 돌리면, 집에 돌아갈 때 모든 값들을 알 수 있었다. 그리고 나머지 자신의 마을에서 X로 가는 건, 모든 노드에 대해서 다익스트라를 돌렸다.. 그리고 그 최단거리 중에서 가장 큰 값을 출력하였다. ## 배운점 어떤 분은 자신의 마을에서 X까지 가는 것을 다익스트라 1번을 돌려서 구하셨다. 방법은 모든 간선의 방향을 뒤집는 것이다. 그러면 출발점을 X로 하는 다익스트라 한번을 통해 모든 마을 까지의 거리를 구할 수 있다. 1234567891011121314151.. 더보기 1956번 1956번 - 운동 싸이클을 구하는 문제이다. 나는 우선 플로이드 워셜 알고리즘을 통해 모든 쌍에 대한 최단거리를 구하였다. 그리고 정점 i 에서 다시 i 로 돌아오는 가장 최단거리는 i 에서 한 정점 k 로 가는 최단거리 + k 에서 다시 i 로 가는 최단거리이기 때문에 이 점을 이용해서 최단거리 싸이클을 구할 수 있었다. ##주의할 점 - i 에서 i 로 돌아오는 값을 처음에 D[i][i] = 0 이라고 놓으면 , 싸이클을 구할 수 없기 때문에, D[i][i] 는 INF 로 초기화 한다 ##다시 깨달은 점 - D[i][i] 를 INF 로 초기화 했기 때문에, 그냥 정답을 D[i][i] 값 중 최소값을 구하면 된다. i 로 돌아오는 싸이클까지 다 계산됨! 12345678910111213141516171.. 더보기 1507번 1507번 - 궁금한 민호 일단 처음에 주어진 입력값을 가지고 플로이드 알고리즘을 다시 수행했다. 그렇게 되면 모든 간선이 연결되어 있게 된다. 그 중에서 이제 삭제할 간선을 선택해야 한다. 삭제할 간선은 i - j 가 있고, i 에서 k를 거쳐서 j 로 가는 i - k - j 가 있다고 할 때, 현재 i 와 k 와 j 정점은 세개의 간선으로 삼각형으로 연결되어 있을 것이다. 그리고 우리는 i - j 의 최단 거리를 안다. 이를 통해 세가지 경우의 수를 알 수 있다. 1번째 경우 - D[i][j] > D[i][k] + D[k][j] 는 불가능한 경우이다. 우리는 D[i][j] 값이 최솟값인 걸 문제에서 줬기 때문이다. 그러므로 -1 출력 2번째 경우 - D[i][j]==D[i][k] + D[k][j] 는.. 더보기 1389번 1389번 - 케빈 베이컨의 6단계 법칙 2달전에 처음 풀 때는 DFS를 이용해서 각각의 사람마다 DFS를 전부 돌렸었다. 그런데 이번에 다시 풀 때는 플로이드 워셜 알고리즘을 통해서 풀 수 있었다. DFS로 풀 때보다 시간이 훨씬 줄었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include using namespace std;int D[101][101];int ans[101];const int INF = 987654321;int main(){ for (int i = 0; i n >> m; for (int i = 0; i > a >> b; .. 더보기 11780번 11780번 - 플로이드 2 11404 플로이드 문제에서 경로를 구하는 문제가 추가되었다. 플로이드 워셜에서 경로를 구할 때는, D[i][j] 값이 갱신 될때, 2차원 via 배열에 k값을 넣는 것이다. 그렇게 된다면 i 에서 j 를 갈때 꼭 k를 거쳐가야 한다는 뜻이 되기 때문에, 이는 i 에서 k 까지, k에서 j 까지의 경로를 구해서 합치면 되기 때문이다. 그래서 makePath 함수에서 이를 재귀를 통해서 구하도록 하였다. 주의할 점은 via 함수를 처음에 -1로 초기화를 시켜줘야 한다는 점이다. 그리고 makePath 에서 중복되는 값들을 처리하기 위해 pop을 한번 시킨다는 것도 주의해야 한다. 마지막으로 출력할 때, 만약 path 에 1개의 값만 들어있다면, 이는 다른 곳으로 갈 수 없다는 .. 더보기 이전 1 ··· 19 20 21 22 23 24 25 ··· 40 다음