어흥
[백준 ] 미네랄 / 미네랄 2 (C++) 본문
문제 링크: https://www.acmicpc.net/problem/2933
2933번: 미네랄
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있
www.acmicpc.net
문제 링크: https://www.acmicpc.net/problem/18500
18500번: 미네랄 2
문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에
www.acmicpc.net
1. 주의할 점
- 높이 H에서 던지는 경우 배열에서 행 - H에서 찾도록 설정하면 된다
- 미네랄 클러스터가 밑으로 이동해야 하는 경우 새로운 배열을 만들어서 해야한다.
제대로 안할경우 밑의 TC가 통과 되지 않는다
9 8
........
...xxx..
.xxx....
.x.x.xxx
.x.x...x
.x.xxx.x
.x.....x
.x.....x
.xxx...x
1
7
- 미네랄 vs 미네랄 2
미네랄 문제는 TC가 상대적으로 적어서 위의 TC를 제대로 처리 못해도 통과가 되며, 이를 해결하기 위해 미네랄2에서는 위의 TC를 제대로 처리해야 통과한다.
2. 구현
- 전형적인 시뮬레이션 문제다. Puyo Puyo의 상위버전이라고 생각한다
- 왼쪽과 오른쪽에서 막대 던질때를 구분해야한다 -> Boolean Left 사용
- 막대를 던졌지만 미네랄에 부딪히지 않은 경우 BFS탐색을 시행하지 않는다
- 막대를 던져서 미네랄에 부딪힌 경우 사라진 미네랄의 4방향 탐색을 통해 미네랄이 있다면 Mineral 벡터에 넣어서 BFS작업을 시행한다
- Mineral에 들어온 미네랄 좌표는 무조건 다른 클러스터의 일부다. Check배열을 미네랄들이 어떤 클러스터에 속한지 나타낸다
- 만약 BFS를 통해 검사중이던 미네랄이 공중에 떠있는 미네랄이라면 더 이상 검사하지 않는다
- 떠 있는 미네랄 클러스터들이 다른 미네랄과 혹은 바닥과의 최소 수직거리를 구한다
- 현재 미네랄맵에서 공중에 떠있는 미네랄 클러스터를 제외하고 모두 Dup배열에 복사한다
- 현재 떠 있는 미네랄 클러스터들을 최소 수직거리만큼 밑으로 내리고, Dup배열에서 내려진 위치로 미네랄을 옮긴다
- 위의 과정을 막대기 던지는 횟수가 끝날때 까지 반복한다.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 3089] 네잎 클로버를 찾아서 (C++) (0) | 2020.03.29 |
|---|---|
| [백준 15558] 점프 게임 (C++) (0) | 2020.03.29 |
| [백준 13023] ABCDE (C++) (0) | 2020.03.26 |
| [백준 1339] 단어 수학 (C++) (0) | 2020.03.26 |
| [백준 16933] 벽 부수고 이동하기 3 (C++) (2) | 2020.03.25 |