[BaekJoon] #11724 - 연결 요소의 개수 [Java][C++]
문제 링크 1. 아이디어 무방향 그래프에서 연결 요소의 개수를 구하는 문제로 BFS나 DFS를 활용해서 각 노드에 대해 방문하지 않았으면 모든 연결된 노드를 방문 처리하고 개수를 하나씩 세도 되며, 유니온 파인드 알고리즘을 활용해서 서로소 집합을 만든 후 집합의 그룹장의 개수를 세어도 된다. 2. 복잡도 접근...
문제 링크 1. 아이디어 무방향 그래프에서 연결 요소의 개수를 구하는 문제로 BFS나 DFS를 활용해서 각 노드에 대해 방문하지 않았으면 모든 연결된 노드를 방문 처리하고 개수를 하나씩 세도 되며, 유니온 파인드 알고리즘을 활용해서 서로소 집합을 만든 후 집합의 그룹장의 개수를 세어도 된다. 2. 복잡도 접근...
문제 링크 1. 아이디어 테스트 케이스별로 9회 동안 각 팀의 점수 합을 더해서 비교만 하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 테스트 케이스 수) 3. 코드 ...
문제 링크 1. 아이디어 사탕을 나누는 것은 몫으로, 남은 사탕은 나머지를 구하는 것으로 간단하게 구할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 테스트 케이스 수) ...
문제 링크 1. 아이디어 주어진 지도에서 섬의 개수를 구하는 문제로 대각선으로 연결되어도 동일한 섬이라서 대각선까지 탐색하는 팔방 탐색을 활용하면 된다. 지도의 각 좌표에 대해 땅이면 해당 땅이 위치한 섬의 모든 땅을 방문 처리를 하는 과정을 반복하는 방식으로 해결할 수 있다. 2. 복잡도 접근 시...
문제 링크 1. 아이디어 주어진 지도의 모든 좌표를 순회하며 집이 있는 곳이면 단지의 크기를 구하고 개수를 세면 된다. 단지의 크기는 BFS나 DFS를 활용해서 구하면 되고 이를 오름차순으로 정렬해서 출력했다. 2. 복잡도 접근 시간 공간 BFS ...
문제 링크 1. 아이디어 치즈는 외부 공기와 두 변 이상 접촉한 경우 한 시간 후에 사라진다. 이때 모눈종이의 가장자리는 치즈가 놓이지 않는 것으로 가정하므로 무한 루프를 돌며 모눈종이 가장자리 중 임의의 좌표에서 BFS를 통해 두 번 이상 치즈가 존재하는 것으로 판단된 좌표들을 찾아서 녹이는 방식으로 해결했다. 치즈가 존재하는 좌표를 발견...
문제 링크 1. 아이디어 주어진 모눈종이에서 직사각형 내부를 제외한 분리된 영역의 개수와 영역의 넓이를 오름차순으로 구하는 문제로 BFS나 DFS를 활용하면 간단하게 해결할 수 있다. 주어진 모눈종이를 시계방향으로 $90^\circ$ 회전했다고 생각하면 행이 $N$, 열이 $M$인 2차원 배열로 생각할 수 있으며, 직사각형이 차지하는 위치를 ...
문제 링크 1. 아이디어 어떤 지역의 높이 정보가 주어졌을 때, 안전 영역의 최대 개수를 구하는 문제로 비의 양에 따른 안전 영역을 전부 구해보면 해결할 수 있다. 안전 영역은 플러드 필을 활용해서 개수를 구할 수 있으며 높이 정보가 1에서 100 사이의 자연수이므로 비의 양을 0부터 99까지 높여가며 탐색해서 최댓값을 갱신해나가면 된다. ...
문제 링크 1. 아이디어 도화지에 있는 그림의 수와 가장 넓은 그림의 넓이를 구하는 문제로 도화지의 각 칸에 대해 그림의 일부이면 BFS나 DFS를 통해 넓이를 구하고 방문 체크를 하면 간단하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 BFS ...
문제 링크 1. 아이디어 적록색약이 아닌 사람은 RGB를 모두 구분하고 적록색약인 사람은 R과 G를 동일하게 볼 때 구역의 수를 구하는 문제로 적록색약이 아닌 사람이면 두 색상이 동일한지를 반환하고, 적록색약인 사람이면 두 색상 중 하나가 B일 때는 두 색상이 동일한지, 아니면 true를 반환하는 색상 비교 함수를 탐색 조건으로 활용했다. ...