백준 알고리즘44 [BOJ]19237번: 어른 상어 www.acmicpc.net/problem/19237 시뮬레이션 문제입니다. 이 문제를 풀 때 가장 중요한 것은 문제 시나리오를 쪼개는 방식이라고 생각합니다. 제가 해결한 순서는 아래 4가지 순서로 문제를 나눠서 해결했습니다. 1. 모든 상어 이동 2. (상어가 이동을 모두 마쳤으니) 기존에 상어가 냄새뿌려놓았던 칸 count-- 3. 상어가 이동 후 겹치는 칸이 있는지 check -> 겹치면 상어 kill 4. 상어가 새로 이동한 칸에 냄새 뿌리기 N제한이 작기 때문에 시뮬레이션으로 구현만 하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19237.cc 2020. 10. 10. [BOJ]19238번: 스타트 택시 www.acmicpc.net/problem/19238 시뮬레이션 문제입니다. N제한과 M제한이 크지 않으므로 다음 손님 탐색과, 손님 이동 모두 BFS로 해결해도 됩니다. 그래도 O(N^2 * M)이 O(20^4) 입니다. 한 가지 빼먹기 쉬운 조건이 "택시가 시작하는 위치와 손님의 시작위치가 같은 경우"가 있다는 것입니다. 이 경우에는 거리를 0으로 하고 처리하면 됩니다. 저는 이 조건 놓쳐서 계속 탐색 시작 거리를 1로 놓고 했다가 많이 틀렸었네요. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19238.cc 2020. 10. 10. [BOJ]18223번: 민준이와 마산 그리고 건우 www.acmicpc.net/problem/18223 다익스트라 응용 문제입니다. 최단 경로 내에 특정 경로가 포함되어 있다면 TRUE, 아니면 FALSE 입니다. 이런 경우에는 before[targetNode]라는 리스트를 만들어서 targetNode 이전에 어디를 방문했었는지 저장해놓습니다. 단, 어떤 노드를 새로 방문을 했을 때 목적지로부터 거리가 갱신되는 경우는 두 가지인데요. 1) 목적지로부터 거리가짧아지는 경우 2) 목적지로부터 거리가 이전과 같은 경우 이렇게 두 가지가 있습니다. 일반 다익스트라면 1번만 저장하면 되지만 지금은 2번도 경우의 수로 따져줘야 합니다. 그러므로 1번의 경우에는 이전에 저장한 before[targetNode]를 전부 지워버리고 새로 시작하고 2번의 경우에는 befo.. 2020. 9. 21. [BOJ]4485번: 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 BFS 등 다양하게 풀 수 있지만 최단 경로를 물어봤으니 다익스트라로 해결하였습니다. (y,x)좌표 하나를 노드로 보게 되면 결국 구해야 하는 건 (0,0) 노드에서 (N-1,N-1) 노드까지의 거리입니다. 이 길이를 갱신해 나가는 방법은 자신와 인접한 4방향을 살펴보며 다익스트라 원리를 적용하면 됩니다. 오른쪽, 아래쪽으로만 가라는 제한조건이 없기 때문에 4방향을 다 훑으면서 최소를 찾아야 합니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ4485.java 2020. 9. 18. 이전 1 2 3 4 5 ··· 11 다음
