https://www.acmicpc.net/problem/6186
6186번: Best Grass
Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 <= R <= 100) rows and C (1 <= C <= 100) columns. She wishes to count the number of grass clump
www.acmicpc.net
문제를 풀면서 몰랐던 개념
- 파이썬의 재귀 최대 깊이 기본 설정에 대한 개념
⬇️⬇️⬇️ 아래 링크 참고 ⬇️⬇️⬇️
- 파이썬의 input 함수와 strip 함수
⬇️⬇️⬇️ 아래 링크 참고 ⬇️⬇️⬇️
문제의 접근 방법
- DFS 알고리즘 사용하기
- 방문한 노드와 방문하지 않은 노드 구분하기
- 입력 받은 그리드를 저장할 수 있는 공간을 만들기
내가 막혔던 부분
- list out of index : input 함수와 strip 함수의 차이를 인지하지 못해서 계속 입력 받는 값들이 리스트 범위 밖으로 측정 됐음.
문제 풀이 방법
(1) 그리드의 높이(R)와 너비(C) 입력 받기
(2) 양과 풀의 정보를 저장할 수 있는 배열(graph) 선언하기
(3) 이중 for 문을 사용하여 높이(R)와 너비(C) 값을 이중 리스트 인덱스로 사용하기
(4) 인덱스에 해당하는 위치에 '#'이 존재한다면 dfs 함수 호출하기
(5) dfs 알고리즘을 사용하기
- 이미 방문한 곳은 '.' (풀)로 바꾸기
- 상하좌우에 또 '#'이 존재하는지 확인한 후, 존재한다면 다시 dfs 함수 호출 or 존재하지 않는다면 반복 루프 벗어나기
- 더 이상의 양 무리를 셀 수 없을 때까지 반복하기(연속으로 붙어있는 #이 더 이상 존재하지 않을 때 <= 이미 방문한 노 드는 '.'으로 바뀌기 때문)
(6) dfs 함수를 빠져나왔다면 count 변수에 +1 하기
(7) (3) ~ (6) 반복한 후 최종 count 값 출력하기
소스코드
import sys
sys.setrecursionlimit(100000)
def dfs(y, x):
graph[y][x] = '.'
dy = [0,1,0,-1]
dx = [1,0,-1,0]
for k in range(4):
ny = y + dy[k]
nx = x + dx[k]
if ny >= 0 and nx >= 0 and ny < R and nx < C:
if graph[ny][nx] == '#':
dfs(ny, nx)
R,C = map(int, input().split())
graph = [list(sys.stdin.readline().strip()) for _ in range(R)]
count = 0
for i in range(R):
for j in range(C):
if graph[i][j] == '#':
dfs(i, j)
count += 1
print(count)
'백준 write-up > 완전 탐색' 카테고리의 다른 글
| [백준] 양 한마리... 양 두마리... : 11123번 - Python (0) | 2022.06.21 |
|---|---|
| [백준] N과 M(1) : 15649번 - Python (0) | 2022.05.29 |
| [백준] 바닥 장식 : 1388번 - Python (0) | 2022.04.04 |
| [백준] 단지번호붙이기 : 2667번 - Python (0) | 2022.01.11 |
| [백준] 그림 : 1926번 - Python (0) | 2022.01.08 |