본문 바로가기

Algorithm/BOJ172

[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.
[BOJ]19236번: 청소년 상어 www.acmicpc.net/problem/19236 시뮬레이션 문제입니다. 어떻게 움직여야하는 지는 문제 꼼꼼히 읽어보면 아실테니 그것보다는 푸시면서 신경써야할 예외케이스에 대해 말하겠습니다. 1. DFS로 푸시든 BFS로 푸시든 매 상태의 2차원 그래프는 서로 분리되어 있어야 합니다. 그냥 매 깊이 갈 때 마다 copy를 하시든, 아니면 가공하고 다시 원상복귀를 하시든 매 상태는 구분되어야 합니다. 즉 탐색하고 빠져나오면 다시 원래 상태에서 다음 탐색을 시작해야된다는 의미입니다. 이게 머릿속에서 꼬이시면 시뮬레이션은 답이 없습니다. 2. 물고기들이 이동하는 시점을 처리할 때 각 물고기는 한 번만 이동해야 합니다. 저 같은 경우는 그냥 2차원 배열 다 뒤지면서 숫자 작은 것부터 이동시켰는데요. //BA.. 2020. 9. 17.
[BOJ]9205번: 맥주 마시면서 걸어가기 www.acmicpc.net/problem/9205 그래프 탐색문제입니다. 상근이네 집 -> 페스티벌 장소까지 중간에 편의점을 경유하든 안하든 도달할 수 있는지 묻습니다. 한 장소에서 맥주를 20개까지 충전가능하기에 정점과 정점사이의 거리가 1000m 이하일 때만 이동 가능합니다. 바꿔말하면, 1. 플로이드 알고리즘을 통해 정점과 정점 사이의 거리를 모두 구하기 2. BFS를 돌면서 상근이네 -> 페스티벌 장소까지 이동가능 여부 판단 위 두 가지 과정을 거치면 됩니다. 다음 노드를 큐에 넣을 수 있는지 판별여부는 현재 노드와 다음 노드의 거리가 1000m 이하인지 체크하면됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ9205.cc 2020. 9. 13.

티스토리툴바