Koala - 18기/코딩테스트 심화 스터디

[백준/python] 6186 Best Grass

ㄱㅈㅅㅇ 2025. 5. 10. 19:00

6186번: Best Grass

그래프 탐색 기본 문제이다.

주변 풀들을 한 묶음으로 여기도록 세야한다.

import sys
input = sys.stdin.readline
from collections import deque

def main(): 
    r, c = map(int,input().split())
    arr = [['.' for i in range(c+2)]]
    for _ in range(r):
        arr.append(['.']+list(input().strip())+['.'])
    arr.append(['.' for i in range(c+2)])

    visit = [[0 for i in range(c+2)] for j in range(r+2)]
    ans = 0

    def graph(i,j):
        # node의 앞뒤좌우로 이어진 #이 있으면 싹 돌면서 비짓체크 
        move = [[-1,0,1,0],[0,-1,0,1]]

        queue = deque()
        queue.append((i,j))
        while queue:
            x,y = queue.popleft()

            for i in range(4):
                    xi = x + move[0][i]
                    yj = y + move[1][i]
                    if arr[xi][yj] == '#' and visit[xi][yj] == 0:
                        visit[xi][yj] = 1
                        queue.append((xi, yj))

    for i in range(1, r+1):
        for j in range(1, c+1):
            if arr[i][j] == '#' and visit[i][j] == 0:
                graph(i,j)
                ans += 1 # 한 뭉치만 1개로 취급
        
    print(ans)

if __name__ == "__main__":
    main()