문제 링크입니다: https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에
www.acmicpc.net
상대적으로 쉬운 문제였습니다.
알고리즘은 아래와 같습니다.
1. vector<pair<int, pair<int, int>>> graph[MAX][MAX] 벡터를 생성하여 해당 좌표에 {상어의 크기, {속도, 방향}}을 추가하는 방식으로 전처리를 진행합니다.
2. 우선, 낚시꾼이 이동하므로 낚시꾼의 x 좌표를 한 칸 움직여줍니다.
3. 낚시꾼이 이동한 x 좌표를 기준으로 y 좌표를 오름차순으로 탐색하며 상어가 있는지 확인하며 제일 먼저 탐색한 상어를 잡고 반복문을 빠져나옵니다.
4. 상어를 이동하는데, 큐에 상어의 좌표와 {상어의 크기, {속도, 방향}}을 넣어주고 해당 좌표에 있는 상어들을 모두 없애줍니다.
5. 큐에 넣은 상어들을 각각의 속도만큼 이동해주는데 벽에 마주할 경우 적절한 인덱싱을 통해 반대방향으로 돌아 움직일 수 있게 해줍니다.
6. 이동한 좌표에 상어를 추가하는데 해당 칸에 이미 자신보다 큰 상어가 있는 경우에는 추가해주지 않고 자신보다 작은 상어가 있으면 해당 상어를 쫒아내고 해당 칸에 들어갑니다.
7. 낚시꾼이 x 범위를 모두 이동할 동안 3 ~ 6번을 반복합니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 12115번 Baza (0) | 2019.05.15 |
|---|---|
| 백준 17144번 미세먼지 안녕! (5) | 2019.05.09 |
| 백준 17142번 연구소 3 (3) | 2019.05.08 |
| 백준 17140번 이차원 배열과 연산 (2) | 2019.05.08 |
| 백준 12904번 A와 B (0) | 2019.05.06 |