오늘은 99클럽 코테 스터디 32일차입니다. 벌써 32일차까지 왔네요. 오늘 문제는 어제 문제와 동일하게 문제가 영어로 되어있습니다. 한 번 오늘 학습한 내용을 살펴볼까요?
1. 오늘의 학습 키워드
- 그래프
- 트리
- DFS
- BFS
2. 문제: Bad Grass (6080번)
- 단계: 🥈실버 2티어
- 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
- 출처: https://www.acmicpc.net/problem/6080
Bad Grass
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 300 | 189 | 173 | 68.379% |
문제
Bessie was munching on tender shoots of grass and, as cows do, contemplating the state of the universe. She noticed that she only enjoys the grass on the wide expanses of pasture whose elevation is at the base level of the farm. Grass from elevations just 1 meter higher is tougher and not so appetizing. The bad grass gets worse as the elevation increases.
Continuing to chew, she realized that this unappetizing food grows the sides of hills that form a set of 'islands' of bad grass among the sea of tender, verdant, delicious, abundant grass.
Bessie donned her lab coat and vowed to determine just how many islands of bad grass her pasture had. She created a map in which she divided the pasture into R (1 < R <= 1,000) rows and C (1 < C <= 1,000) columns of 1 meter x 1 meter squares. She measured the elevation above the base level for each square and rounded it to a non-negative integer. She noted hungrily that the tasty grass all had elevation 0.
She commenced counting the islands. If two squares are neighbors in any of the horizontal, vertical or diagonal directions then they are considered to be part of the same island.
How many islands of bad grass did she count for each of the supplied maps?
입력
- Line 1: Two space-separated integers: R and C
- Lines 2..R+1: Line i+1 describes row i of the map with C space separated integers
출력
- Line 1: A single integer that specifies the number of islands.
예제 입력 1
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
예제 출력 1
2
힌트
There are two islands. The big one on the left side that extends all the way to the bottom through a diagonal and the small one on the upper-right corner.
3. 나의 풀이
오늘도 문제 이해가 쉽지 않군요.. 그래도 한 번 차근차근 분석해볼까요?
문제 분석
문제 분석을 먼저 진행해보겠습니다.
Bessie는 목초지에서 나쁜 풀의 섬 개수를 세고자 합니다. 이 나쁜 풀 섬은 1m x 1m 크기의 정사각형으로 일종의 grid형태라고 보면 됩니다. 나쁘지않고 좋은 풀의 섬ㅇ의 고도는 0, 나쁜 풀의 섬의 고도는 0보다 큰 값이라 보면 될 것 같습니다.
초원은 사각형의 형태이고 각 grid는 섬을 나타내고 , 여기서 나쁜 섬 (grid)을 찾는 것이 문제라 볼 수 있습니다.
이 섬 (grid)들은 서로서로 모두 연결되어 있기 때문에, 그래프의 connected component라 볼 수 있으며, 이 연결 요소들을 탐색하면서 나쁜 섬을 찾는것이 문제이므로 그래프 탐색 알고리즘인 BFS와 DFS를 사용할 수 있습니다.
접근 방법
주어진 문제는 2차원 그리드에서 특정 조건을 만족하는 연결된 컴포넌트(섬)의 개수를 세는 문제입니다. 이 문제는 일반적으로 그래프 탐색 문제로 분류되며, DFS 또는 BFS를 사용하여 해결할 수 있습니다. 이 문제에서 중요한 포인트는:
- 연결된 컴포넌트: 서로 인접한 셀들이 연결된 하나의 그룹을 형성합니다.
- 인접한 셀: 상하좌우 및 대각선으로 인접한 셀들로 구성됩니다.
DFS를 통한 해결
DFS를 사용하면 한 셀에서 시작하여 가능한 모든 방향으로 깊이 탐색을 진행하면서 연결된 모든 셀을 방문할 수 있습니다. 이 과정은 재귀적으로 구현할 수 있지만, 스택을 사용한 반복적 접근이 더 효율적일 수 있습니다. 모든 연결된 셀을 방문한 후에는 새로운 컴포넌트(섬)를 탐색하기 위해 탐색을 계속합니다.
BFS를 통한 해결
BFS를 사용하면 시작 셀에서 가까운 셀부터 탐색하며, 동일한 레벨의 셀을 먼저 모두 방문한 후 다음 레벨로 이동합니다. 이 과정은 큐를 사용하여 구현됩니다. BFS의 특징인 너비 우선 탐색은 최단 경로 문제에 유리하지만, 이 문제에서도 연결된 컴포넌트를 찾는 데 효과적입니다.
참,, 이게 반복 숙달이 되면 쉬울거 같은데 비기너 수준인 제 입장에선 문제를 이해하고 어떤 알고리즘을 적용시키는데에 많은 시간이 소요되었습니다. 그럼 이제 코드를 살펴볼까요?
DFS(재귀적) 접근
코드 설명:
DFS(Depth-First Search, 깊이 우선 탐색)는 그래프 탐색에서 가장 기본적인 방법 중 하나입니다. 재귀를 사용하여 탐색을 구현할 수 있으며, 이는 스택 자료구조를 활용한 것과 같은 효과를 줍니다. 코드에서는 재귀적으로 상하좌우 및 대각선 방향으로 연결된 모든 셀을 방문합니다.
import sys
sys.setrecursionlimit(10**6) # 재귀 깊이를 충분히 큰 값으로 설정
def count_bad_grass(grid, R, C):
def dfs(r, c): # r: 행, c: 열
if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0:
return
grid[r][c] = 0
dfs(r-1, c) # 상
dfs(r+1, c) # 하
dfs(r, c-1) # 좌
dfs(r, c+1) # 우
dfs(r-1, c-1) # 좌상 대각선
dfs(r+1, c+1) # 우하 대각선
dfs(r+1, c-1) # 좌하 대각선
dfs(r-1, c+1) # 우상 대각선
cnt = 0
for r in range(R):
for c in range(C):
if grid[r][c] > 0:
dfs(r, c)
cnt += 1
return cnt
- 재귀 호출: 재귀 함수
dfs는 현재 위치에서 인접한 모든 방향으로 이동하며 연결된 모든 나쁜 풀을 탐색합니다. 이미 방문한 셀은 0으로 표시하여 다시 방문하지 않도록 합니다. - 기저 조건: 그리드의 범위를 벗어나거나, 고도가 0인 셀에 도달하면 재귀를 종료합니다.
- 시간 복잡도: 이 알고리즘의 시간 복잡도는 O(R * C)로, 그리드의 모든 셀을 한 번씩 방문합니다.
- 이 코드는 sys.setrecursionlimit(10**6)을 설정하지 않으면
RecursionError에러가 나와 통과하지 못했습니다.
DFS(스택 사용) 접근
코드 설명:
재귀 깊이가 깊어지면 RecursionError가 발생할 수 있으므로, 스택을 명시적으로 사용하여 반복문 기반의 DFS를 구현할 수도 있습니다. 이 방법은 스택 자료구조를 사용해 재귀 없이 깊이 우선 탐색을 수행합니다.
import sys
from collections import deque
def count_bad_grass(grid, R, C):
def dfs_stack(r, c):
stack = deque([(r, c)])
while stack:
r, c = stack.pop()
if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0:
continue
grid[r][c] = 0
stack.append((r-1, c))
stack.append((r+1, c))
stack.append((r, c-1))
stack.append((r, c+1))
stack.append((r+1, c+1))
stack.append((r-1, c-1))
stack.append((r+1, c-1))
stack.append((r-1, c+1))
cnt = 0
for r in range(R):
for c in range(C):
if grid[r][c] > 0:
dfs_stack(r, c)
cnt += 1
return cnt
- 스택 사용: 스택을 사용해 DFS를 구현합니다. 스택을 사용해 현재 위치에서 가능한 모든 방향으로 이동하면서, 연결된 나쁜 풀을 탐색합니다.
- 스택 기반 반복문: 재귀 대신 반복문을 통해 스택을 관리하며, 스택이 빌 때까지 탐색을 계속합니다.
- 안전한 재귀 대안: 이 방법은 재귀 깊이 제한에 걸리지 않으므로, 큰 입력에 대해서도 안정적으로 동작합니다.
BFS(너비 우선 탐색) 접근
코드 설명:
BFS(Breadth-First Search, 너비 우선 탐색)는 큐를 사용하여 구현합니다. BFS는 너비를 우선으로 탐색하기 때문에, 시작점에서 가까운 셀들부터 차례로 탐색합니다.
import sys
from collections import deque
def count_bad_grass(grid, R, C):
def bfs_queue(r, c):
queue = deque([(r, c)])
while queue:
r, c = queue.popleft()
if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0:
continue
grid[r][c] = 0
queue.append((r-1, c))
queue.append((r+1, c))
queue.append((r, c-1))
queue.append((r, c+1))
queue.append((r+1, c+1))
queue.append((r-1, c-1))
queue.append((r+1, c-1))
queue.append((r-1, c+1))
cnt = 0
for r in range(R):
for c in range(C):
if grid[r][c] > 0:
bfs_queue(r, c)
cnt += 1
return cnt
- 큐 사용: BFS는 큐를 사용하여 탐색을 수행합니다. 시작점에서 가까운 셀들부터 차례대로 탐색하며, 모든 인접한 셀을 탐색할 때까지 반복합니다.
- 너비 우선 탐색: BFS는 한 번에 하나의 레벨씩 탐색하므로, 탐색 순서가 넓게 퍼집니다.
- 경우에 따른 사용: BFS는 일반적으로 최단 경로 문제에 사용되지만, 이 문제에서도 효과적으로 연결된 셀들을 찾을 수 있습니다.
시간복잡도를 살펴볼까요?
세 가지 코드 모두 이론적인 시간 복잡도는 동일합니다. 각 접근 방법의 시간 복잡도를 살펴보면 다음과 같습니다:
시간 복잡도 분석:
- DFS (재귀적 구현)
- DFS (스택 사용)
- BFS (큐 사용)
이 세 가지 접근법 모두 *O(R ** C)의 시간 복잡도를 가집니다.
왜 동일한 시간 복잡도를 가지는가?
- 그리드의 모든 셀을 한 번씩 방문:
- 각 방법은 그리드의 모든 셀을 한 번씩 방문합니다. 나쁜 풀이 있는 셀을 방문하면, 그 셀을 기준으로 인접한 셀을 탐색하여 섬 전체를 탐색합니다.
- 한 번 방문한 셀은 다시 방문하지 않도록 처리하기 때문에, 그리드의 모든 셀을 총 한 번씩만 탐색하게 됩니다.
- 연결된 셀의 탐색:
- DFS와 BFS 모두 각 셀을 방문할 때 인접한 셀(상하좌우 및 대각선 8방향)을 탐색합니다. 인접한 셀이 고도 0보다 큰 경우에만 스택(또는 큐)에 추가되고, 방문 처리됩니다.
- 탐색 반복:
- 모든 셀을 방문하고, 연결된 나쁜 풀 섬을 찾기 위해 반복적으로 탐색을 수행합니다. 이 과정은 그리드의 크기, 즉 R * C에 비례하는 시간 복잡도를 갖습니다.
세 가지 접근법 모두 그리드의 크기에 비례하는 시간 복잡도를 가지므로, 이론적으로는 동일한 O(R C)**시간 복잡도를 가집니다.
다만, 실제 실행 시간에서는 스택과 큐의 관리 방식이나 재귀 호출에 따른 오버헤드가 약간의 차이를 만들 수 있습니다. 예를 들어, 스택과 큐를 사용하는 반복적 접근 방식이 재귀보다 더 효율적일 수 있습니다. 하지만 이런 차이는 문제의 크기에 따라 미세한 차이일 뿐이며, 기본적인 시간 복잡도는 동일하다고 볼 수 있습니다.
실제로도 결과 차이를 살펴보겠습니다:
제일 위에 있는 결과는 BFS 알고리즘의 결과입니다. 새번째는 DFS 스택을 활용했을때의 결과, 4번째 결과는 DFS 재귀를 활용했을 때의 결과입니다.
그 밑에 보시면 Recursion Error가 보이시죠? sys.setrecursionlimit 설정을 하지 않았을 때 나온 결과입니다.
위 결과를 보시면 이 문제는 BFS 알고리즘을 사용했을 때 메모리나 시간 모두 가장 효율적인것을 확인할 수 있습니다.
4. 결론
이번 포스트에서는 같은 문제를 다양한 방법으로 해결하는 세 가지 접근법을 살펴보았습니다. DFS와 BFS는 각각의 장단점이 있으며, 문제의 특성에 따라 적절한 방법을 선택하는 것이 중요합니다. 코딩 테스트에서 이들 알고리즘을 효과적으로 활용할 수 있도록, 충분한 연습이 필요합니다.
역시 반복만이 살 길이군요.,
전체 코드는 제 깃허브에서 확인하실 수 있습니다.
질문은 언제나 환영입니다!! 도움이 되셨다면 좋아요, 팔로우 부탁드립니다.
읽어주셔서 감사합니다!
😶 TMI:) 다시 매우, 엄청 바빠질거 같네요,, 취준은 언제하냐…!!
