[DFS/BFS]99클럽 코테 스터디 32일차 TIL + 백준/Silver/양 한마리... 양 두마리...

[Silver II] 양 한마리... 양 두마리... - 11123

문제 링크

성능 요약

메모리: 31120 KB, 시간: 264 ms

분류

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

제출 일자

2024년 8월 24일 18:18:09

문제 설명

얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" 정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

입력

첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.

이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진

하나를 입력받는다.

• 0 < T ≤ 100
• 0 < H, W ≤ 100

출력

각 테스트 케이스마다, 양의 몇 개의 무리로 이루어져 있었는지를 한 줄에 출력하면 된다.

 

 

 

<내 코드>

def find_is_lamb_by_dfs(grid, row, column):

    directins = [(0,-1),(0,1),(1,0),(-1,0)]

    def dfs(x, y):
        stack = [(x, y)]

        while stack:
            cx,cy = stack.pop()

            if grid[cx][cy] == ".":
                continue

            grid[cx][cy] = "."

            for dx,dy in directins:
                nx, ny = cx + dx, cy + dy

                #for loop 밖에 있었음
                if (0 <= nx < row) and (0 <= ny < column) and (grid[nx][ny] == "#"):
                    stack.append((nx,ny))

    lamb_count = 0
    for i in range(row):
        for j in range(column):
            if grid[i][j] == "#":
                dfs(i, j)
                lamb_count += 1

    return lamb_count


if __name__ == "__main__":

    test_case = int(input())

    for _ in range(test_case):
        # row, colum 갯수 입력 받음
        R, C = map(int, input().split())

        grid = []

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

        result = find_is_lamb_by_dfs(grid, R, C)
        print(result)

- 그전 섬 갯수 구하기 문제와 방향성이 거의 일치하기 때문에 코드를 조금만 고치면 됐음

 

- 문자열을 입력할 때 에는

grid.append(list(input())) 이것과 grid.append(input())

두개 차이를 잘 이해해야함

전자의 경우 가변성으로서 #을 . 으로 변경할 수있지만, 후자는 불변성으로 불가능함

 

- dfs 에 대한 감이 올라오고있음