반응형 Problem Solving242 백준 2162번 선분 그룹 - 스위프트(Swift) 풀이 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 2. union 과정에서 집합의 크기를 기록한다. 3. 전체 집합의 개수와 가장 큰 집합의 크기를 출력한다. 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 서로 만나는 두 선분을 같은 그룹으로 묶어주어야 한다. 유니온 파인드의 union 연산을 해준다. 선분 교차 알고리즘은 17387번에서 썼던 걸 그대로 썼다. 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. union 과정에서 집합의 크기를 기록한다. 마지막에 가장 큰 그룹의 크기를 출력해야 하기 때문에 union 과정에.. 2022. 2. 7. 백준 1799번 비숍 - 스위프트(Swift) 풀이 + 그림 설명 1. 백트래킹으로 비숍을 하나씩 놓아본다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다. 1. 백트래킹으로 비숍을 하나씩 놓아본다. 비숍을 하나씩 놓아본다. 각 칸을 순차적으로 순회하면서 해당 칸에 비숍을 놓는 경우와 놓지 않는 경우를 다 해보면 된다. 다음칸으로 넘어갈 때는 비숍의 경로가 겹치면 안 되기 때문에 현재 체스판의 상황을 같이 넘겨주어야 한다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 현재 체스판 상태를 N*N짜리 배열로 넘겨주는 것은 비효율적이다. 어차피 비숍은 대각선으로만 이동할 수 있으므로, 대각선마다 비숍이 위치하는지 여부만 넘겨주자. 현재 칸이 속한 두 종류의 대각선을 모두 확인해서, 두.. 2022. 2. 6. 백준 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. 백준 16946번 벽 부수고 이동하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 2. union 할 때 각 집합의 크기를 기록해둔다. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 빈칸들이 인접해있으면 인접한 빈칸을 모두 방문할 수 있다. 따라서 인접한 빈칸들을 유니온 파인드를 사용해 하나의 집합으로 처리해준다. 2. union 할 때 각 집합의 크기를 기록해둔다. 방문할 수 있는 빈칸의 개수를 알아야 하기 때문에 각 집합의 크기를 구해둬야 한다. 두 집합을 union 할 때 크기도 같이 합쳐서 기록해두자. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 어떤 벽을 부수면, 벽 때문에 막혀있던 상하좌우 칸들이 연결되게 된다. 따라서 어떤 벽을 부쉈을 때 방문.. 2022. 2. 5. 백준 16724번 피리 부는 사나이 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 2. 이미 방문한 점이더라도 Union은 하고 넘어간다. 3. 집합의 개수가 곧 SAFE ZONE의 개수이다. 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 어떤 칸들이 하나의 경로로 이어져있다면 결국 경로 중 어느 칸에서 출발하더라도 계속 가다 보면 그 경로의 끝 칸에 도달하게 된다. 따라서 그 끝 칸에만 SAFE ZONE을 설치하면 된다. 한 경로로 이어져 있는 칸들을 하나의 집합으로 처리하기 위해 유니온 파인드를 사용한다. DFS를 돌면서 한 경로로 이어져있는 칸들을 모두 union 해준다. 2. 이미 방문한 점이더라도 Uni.. 2022. 2. 5. 이전 1 ··· 33 34 35 36 37 38 39 ··· 49 다음 반응형
