[DFS/BFS]99클럽 코테 스터디 30일차 TIL + 백준/Silver/6080. Bad Grass

[Silver II] Bad Grass - 6080

문제 링크

성능 요약

메모리: 196500 KB, 시간: 904 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 22일 19:41:02

문제 설명

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.

 

<내코드 호소>

def find_is_islands(grid, R, C):

    #
    def iterative_dfs(x, y):
        # 깊이 우선 탐색 위한 스택으로 x,y 튜플 선언
        stack = [(x, y)]

        while stack:
            cx, cy = stack.pop()
            # 바다이면 나감
            if grid[cx][cy] == 0:
                continue

            # 방문표시
            grid[cx][cy] = 0

            # in 부분 순서대로 : 상하 / 좌우 / 좌하, 좌상, 우하, 우상
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                # 현재 위치에서 dx, dy 부분만큼 더함 (상하 좌우 대각선에 이웃 탐색)
                nx, ny = cx + dx, cy + dy
                # 이웃이 그리드 안에 있고, 1이상 이라면 stack 에 넣어줌
                if (0 <= nx < R) and (0 <= ny < C) and (grid[nx][ny] > 0):
                    stack.append((nx, ny))

    island_count = 0

    # 2중반복문으로 grid 탐색
    for i in range(R):
        for j in range(C):
            # i row에 대한, j column 을 탐색하면서 0 이상 풀 부분에 대해서 탐색 시작
            if grid[i][j] > 0:
                # dfs 실행
                # 이것 한번 실행하면 연결된 섬은 모두 0으로 바뀜 (방문표시) -> 이후 다른 비방문 노드에 dfs 실행
                iterative_dfs(i, j)
                island_count += 1

    return island_count

if __name__ == "__main__":

    # row, colum 갯수 입력 받음
    R, C = map(int, input().split())

    grid = []

    # row 수만큼 반복문으로 입력을 받음
    # 각 row 마다 리스트 입력을 받음
    for _ in range(R):
        grid.append(list(map(int, input().split())))

    result = find_is_islands(grid, R, C)

    print(result)

 

1. 포인트

- 그리드 밖 부분에 대한 처리

=> 이 부분에 대해서 꼼꼼히 보아야함

 

- 재귀 횟수 경과

=> 반복문으로 하는게 좋을수도

 

- 그리고 맞춤 4방향 이동방법

=> 꼼꼼히 생각해야함