반응형 시뮬레이션15 백준 14891번 톱니바퀴 - C++(cpp) 풀이 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 인접하면서 맞닿는 극이 반대인 톱니바퀴로만 전이가 일어날 수 있으므로, 그런 톱니바퀴들끼리만 간선으로 연결되어있다고 생각하자. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 회전 쿼리가 주어질 때마다 DFS로 회전의 전이를 시뮬레이션하면 된다. 전이는 회전하기 전의 상태를 기준으로 결정되기 때문에 rotate를 재귀 호출 이후에 실행해.. 2022. 3. 11. 백준 3055번 탈출 - C++(cpp) 풀이 1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다. 2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다. 3. 2번 과정에서 비버의 굴에 도착하면 그 시간을 출력한다. 1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다. 물이 매 분 인접한 한 칸으로 확장되므로 너비우선탐색(BFS)로 시뮬레이션 할 수 있다. BFS에서의 depth가 곧 해당 칸에 물이 도착하기까지 걸리는 시간이다. 2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다. 고슴도치도 매 분 인접한 한 칸으로 이동하므로 BFS로 시뮬레이션할 수 있다. 인접한 칸으로.. 2022. 2. 17. 백준 16234번 인구 이동 - 스위프트(Swift) 풀이 1. 인접한 두 칸의 차이가 L 이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 3. BFS가 하나도 이루어지지 않으면 이동이 끝난 것이다. 1. 인접한 두 칸의 차이가 L이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 현재 상황을 그래프로 바꾸어줄 것이다. 각 칸을 정점으로 생각하고, 인접한 두 칸(정점)의 인구수 차이가 L 이상 R이하라면 두 정점을 연결해준다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 인구 이동 시뮬레이션을 진행해준다. 하루가 지날 때마다 BFS로 인접한 정점들을 연합으로 만든 뒤, 인구 이동을 처리해준다. BFS 과정에서 방문한 국가들을 배열에 담아두었다가 마지막에 배열을 순회하면서 평균 인구수.. 2022. 2. 12. 백준 17143번 낚시왕 - 스위프트(Swift) 풀이 + 그림 설명 1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다. 2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다. 3. 상어들을 이동시킬 때 딕셔너리를 이용해서 위치가 중복되면 가장 큰 상어만 남긴다. 1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다. 먼저 한 열 오른쪽으로 이동한 뒤 상어를 잡는다. 잡아야 할 상어는 모든 상어를 순회해서 결정한다. 한번 상어를 잡을 때 O(RC)의 시간복잡도가 든다. 2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다. s가 최대 1,000까지 가능하다. 1,000칸을 시뮬레이션으로 모두 이동시킬 경우 상어 이동에만 O(1000*RC)의 시간 복잡도가 들게 되어 시간 초과가 발생한다. 각 상어를 O(1)에, 즉 모든 상어 .. 2022. 2. 5. 백준 12100번 2048 (Easy) - 스위프트(Swift) 풀이 + 그림 설명 1. 미는 방향으로 블록을 몬다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 3. 합치면서 생긴 빈자리를 없앤다. 4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다. 1. 미는 방향으로 블록을 몬다. 아래와 같은 보드 상태에서 위로 밀어야 하는 상황이다. 열 별로 차례로 밀어줄 것이다. 1열부터 밀어보자. 먼저 빈 공간이 없도록 윗방향으로 블록들을 몰아준다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 이제 합칠 차례이다. 만약 인접한 두 블록을 합칠 수 있는 경우 합친다. 미는 방향이 윗방향이기 때문에 윗블록이 남고 아랫 블록은 사라진다. 3. 합치면서 생긴 빈자리를 없앤다. 합치면서 생긴 빈자리를 또 메꿔주면 미는 작업이 끝난다. 나.. 2022. 1. 29. 이전 1 2 3 다음 반응형
