반응형 dfs26 백준 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. 백준 2638번 치즈 - 스위프트(Swift) 풀이 + 그림 설명 1. 가장자리 아무 칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 3. 치즈가 남지 않을 때까지 1-2를 반복한다. 1. 가장자리 아무칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 가장자리에는 치즈가 오지 않으므로 항상 외부 공기가 있는 칸이다. 치즈로 둘러싸여 있는 내부 공기 칸과 구분하기 위해 매시간마다 가장자리에서 시작하는 BFS/DFS를 돌면서 인접한 칸들을 모두 외부 공기 칸으로 처리해준다. 좌측과 같은 초기 상황이라고 하면, 먼저 우측 그림처럼 외부 공기 처리를 해준다. 내부 공기와는 다르게 처리되고 있는 것에 유의한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 매 시간마.. 2022. 1. 26. 백준 10026번 적록색약 - 스위프트(Swift) 풀이 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 구역 내의 모든 칸을 방문할 수 있다. 4. 따라서 DFS/BFS의 호출 횟수가 곧 구역의 개수이다. 5. 적록색약인 경우 그리드의 R과 G를 같은 색으로 취급해준다. 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 그리드 전체를 그래프로 생각할 수 있다. 각 칸을 정점으로 둔다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 상하좌우로 인접한 칸이 같은 색이면 같은 구역이므로, 간선으로 연결해준다. 이러면 같은 구역인 정점끼리만 간선으로 연결될 것이다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 .. 2022. 1. 18. 백준 2667번 단지번호붙이기 - 스위프트(Swift) 풀이 + 그림 설명 1. 각 집을 그래프의 정점으로 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. 3. 따라서 DFS/BFS의 호출 횟수가 곧 단지의 개수이고, 4. DFS/BFS를 돌면서 방문한 정점의 수가 한 단지 내에 속한 집의 수이다. 1. 각 집을 그래프의 정점으로 생각한다. 0인 곳은 갈 수 없으므로 무시하고, 1인 곳을 정점이라고 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. (1, 1)을 시작점으로 그래프를 탐색해주면, 해당 단지 내의 모든 집을 방문할 수 있다. 탐색 방법은 DFS/BFS를 쓰면 된다. 이때 연결되지 않은 (1,4)와 (2,4)가 속한 단지는 방문을 하지.. 2022. 1. 17. 이전 1 2 3 4 5 6 다음 반응형
