[백준|파이썬] 6186: Best Grass (실버5)

문제

https://www.acmicpc.net/problem/6186

6186번: Best Grass

 

 

🐍파이썬

BFS를 이용한 풀이

import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
grass = []
for _ in range(r):
    grass.append(list(sys.stdin.readline().rstrip()))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    grass[x][y] = "."
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= r or ny >= c or nx < 0 or ny < 0:	#배열범위를 벗어난 경우 건너뛰기
                continue
            if grass[nx][ny] == ".":	#값이 .인 경우 건너뛰기
                continue
            if grass[nx][ny] == "#":	#값이 #인 경우
                grass[nx][ny] = "."	#방문했으니 다른 값으로 덮어씌우기
                queue.append((nx, ny))	#nx, ny를 기준으로 순회할 수 있도록 nx, ny를 queue에 넣어준다.
answer = 0
for i in range(r):
    for j in range(c):
        if grass[i][j] == "#":
            bfs(i, j)
            answer += 1
print(answer)

한 개 이사의 "#"이 연속으로 존재하는 구역의 갯수를 찾는 문제이다.

이전에 풀었던 배추 풀이와 동일한 풀이방식으로 풀었다. ([백준 알고리즘] 1012: 유기농 배추(파이썬))

 

1️⃣ grass에서 값이 "#"인 지역을 찾으면 BFS를 통해 그 지역의 상하좌우를 순회하며 또 다른 "#"이 존재하는지 확인한다.

2️⃣ "#"이 존재한다면 해당 지역을 "."으로 덮어씌움으로써 이미 발견되었던 구역은 다음 번에 중복체크하지 않도록 한다.

3️⃣ 가능한 범위에서 "#"을 모두 찾았다면 BFS 함수를 종료하고 구역의 갯수 + 1을 통해 구역 갯수 체크를 진행한다.

4️⃣ 모든 지역에 대한 탐색을 마쳤다면, 체크된 구역의 갯수를 프린트한다.

 

 

다른 풀이 방법

DFS를 이용한 풀이

import sys
input = sys.stdin.readline

def dfs(x, y):
    v[x][y] = 1	#방문체크
    for i in range(4):
        tx, ty = x + dx[i], y + dy[i]
        if 0 <= tx < r and 0 <= ty < c:	#배열의 범위 내에서만 dfs 진행
            if not v[tx][ty] and a[tx][ty] == '#':
                dfs(tx, ty)	#재귀를 통해 이어진 "#"을 모두 찾는다


r, c = map(int, input().split())
a = [list(input().strip()) for _ in range(r)]
v = [[0]*c for _ in range(r)]	#방문여부를 체크하는 리스트
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
ans = 0
for i in range(r):
    for j in range(c):
        if not v[i][j] and a[i][j] == '#':	#방문한 적 없고 값이 "#"이라면
            dfs(i, j)
            ans += 1
print(ans)