Problem Solving/그래프_최단 거리 썸네일형 리스트형 BOJ 16236 - 아기 상어 문제 링크(Link)https://www.acmicpc.net/problem/16236 문제 해결(Solution) 반복적인 BFS와 Sort를 이용해서 문제를 해결한다. 단, 구현이 까다롭다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 생각해야하는 조건 : 이 문제는 생각해야하는 조건들이 많다. 그 중 가장 까다로운 것이 '어떤 물고기를 먹을 것인가?' 다. 이는 vector를 이용해서 쉽게 해결할 수 있다. vector를 해서 거리, row, col 순으로 저장하면 단순한 sort함수를 통해서 다음에 먹을 물고기를 쉽게 찾을 수 있다. 2. 시간 복잡도는? : 인접행렬로 구현했기 때문에 BFS는 N^2, sort() 함수를 사용했기 때문에 정렬은 NlgN. 그러므.. 더보기 BOJ 4179 - 불! 문제 링크(Link)https://www.acmicpc.net/problem/4179 문제 해결(Solution) BFS를 응용한 문제. 지훈이가 아무리 돌아다녀도 미로를 넘어서는 계속해서 이동할 수 없으므로, 시간복잡도는 O(R*C)이다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 사람과 불의 이동에 대해서 잘 생각해야한다. 같은 시간에 불과 사람이 같은 곳에 도착한다면, 사람이 그 곳을 지나갈 수 없다고 생각해야햔다. 즉, 불의 우선순위가 사람의 우선순위보다 높다고 생각해야한다. 2. 불의 좌표를 다루는 queue와 사람의 좌표를 다루는 queue를 별개로 관리한다. 그 과정에서 우선순위를 생각해 불의 이동을 우선으로 한다. 참고(Reference) - ※ 정확하.. 더보기 BOJ 2206 - 벽 부수고 이동하기 문제 링크(Link)https://www.acmicpc.net/problem/2206 문제 해결(Solution) 1. BFS의 응용문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 만약 벽의 좌표를 모두 저장한 후, 하나씩 부수며 BFS를 하면 시간복잡도 O(NM(N+M))이 되므로 시간 초과를 받을 수 밖에 없다. 2. 보통은 2차원 배열을 이용해서 문제를 해결하지만, 이 문제는 3차원 배열을 이용하면 단 한번의 BFS를 통해서 답을 구할 수 있다. 3. dist[i][j][k] = (i, j)에서 k가 1이면 벽을 만나서 부수고 이동, k가 0이면 벽을 만나면 이동 불가. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 9370 - 미확인 도착지 문제 링크https://www.acmicpc.net/problem/9370 문제 해결 1. 최단 거리를 구하는 문제. 2. 시작점과 도착점이 될 수 있는 후보 점들이 주어진다. 도착점이 되기 위해선, 반드시 g와 h 사이의 간선을 지나야한다. 3. dist1[i] = 시작점으로부터 모든 점까지의 최단 거리. dist2[i] = dist1[g]와 dist1[h] 중 가까운 점 g 또는 h로부터 모든 점까지의 최단 거리 4. 도착점이 될 수 있는 점 t가 있을 때, dist1[t] == dist1[min(dist1[g],dist1[h])인 점] + dist2[t] 이 되는 t를 오름차순으로 출력 주의할 점 || 생각해볼 점 1. testcase마다 graph를 초기화시키는 과정에서 실수가 있었다. 항상 조심.. 더보기 이전 1 다음