문제 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 문제의 요구상을 그대로 구현하면 된다. 비슷한 시뮬레이션 문제로는 어른 상어이지 않을까 싶다. 이전에 다룬 문제보다 까다로운 것은 체스 말이 중첩되는 경우, 그대로 쌓인다는 것이다. 또한 이동할 때 현재 체스 말의 번호와 쌓인 체스 말들을 판단하여서 이동시켜야 한다는 것이 달랐다. 여기에 초기에 주어지는 정보에 흰색, 빨간색, 파란색의 색깔이 구분되는 칸이 주어지면 각 칸들에 따라 다르게 동작하여야 한다. 흰색인 경우 그대로 이동한다. 빨간색인..
문제 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 문제 풀이 상어의 위치와 상어의 방향이 주어진다. 이때 각 상어들은 이동하며 냄새를 뿌리고, 이동한다. 그리고 뿌려진 냄새는 K초가 지나면 사라진다. 이는 간단하게 생각하면 1) 냄새 뿌리기, 2) 상어 이동, 3) 시간에 따른 냄새 감소로 나누어 그대로 구현하면 된다. 하지만 문제를 풀면서 3가지 문제를 맞이하며 푸는데 시간이 지연되었다. 동일한 자리에 여러 마리의 상어가 들어가는 경우, 가장 작은 번호를 가진 ..
백준: 17779 게리멘더링 2
문제 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 풀이 문제를 접하고 나서, 이게 무슨 말이지?😅 하며, 문제를 여러 번 읽어보았다. 하나의 구역(r, c)을 기준으로 `r, c, d1, d2`에 따라 5번 선거구의 크기가 달라지게 된다. 적절히 경계를 조정하여, 선거구마다 최대한 공평하게 인원이 나누어지도록 해야 하는 문제이다. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 다음 칸은 경계선..
문제 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 풀이 문제를 단순하게 보면, 첫 번째 BFS를 탐색을 통해 택시의 위치로부터 손님의 위치까지 최단 거리를 찾는다. 그리고 두 번째 BFS 탐색을 통해 손님의 목적지까지 도달할 수 있는지를 찾는다. 단순히 BFS를 두 번 생각한다고 생각하면 쉽지만 문제에 제시되는 조건들을 지켜야 한다. 택시와 손님과의 거리를 찾고, 거리가 가까운 손님부터 태운다. 손님이 있는 곳 까지 이동 가능한 경우 거리가 같은 손님이 여러 명일..
