Algorithm283 [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. [BOJ]1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net/problem/1389 BFS, 플로이드-와샬 등 다양한 형태로 해결할 수 있습니다. 저는 플로이드로 해결했습니다. "dist[i][j] = i와 j가 연결되어 있는 거리"로 정의합니다. 초기값은 dist[i][j]= ∞로 두고, 입력이 주어져 있는 경우만 dist[i][j] = 1로 셋팅을 합니다. 그 다음에 플로이드를 돌면서 dist[i][j] > dist[i][mid] + dist[mid][j] 이면 dist[i][j] = dist[i][mid] + dist[mid][j] 로 갱신하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1389.cc 2020. 9. 12. [BOJ]1613번: 역사 www.acmicpc.net/problem/1613 역사의 우선순위는 그래프 문제로 바라볼 수 있습니다. 그래프 문제 관점에서 모든 정점에서 다른 모든 정점으로의 관계가 궁금한 것이니 플로이드 알고리즘을 써서 해결할 수 있습니다. eventTable[eventA][eventB] == 1 이면, eventA가 B보다 먼저 일어난 것이고, eventTable[eventB][eventA] == 1 이면, eventB가 A보다 먼저 일어난 것이고, eventTable[eventA][eventB] == 0 이면, 둘 사이에는 아무런 관계가 없는 것입니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1613.cc 2020. 9. 11. 이전 1 ··· 29 30 31 32 33 34 35 ··· 71 다음
