[백준] 양 한마리... 양 두마리... : 11123번 - Python

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

11123번: 양 한마리... 양 두마리...

 

 

 

문제를 풀면서 몰랐던 개념

 

- 파이썬의 재귀 최대 깊이 기본 설정에 대한 개념

 

⬇️⬇️⬇️ 아래 링크 참고 ⬇️⬇️⬇️

https://ye5ni.tistory.com/178

 

 

 

문제의 접근 방법

 

- DFS 알고리즘 사용하기

- 방문한 노드와 방문하지 않은 노드 구분하기

- 입력 받은 그리드를 저장할 수 있는 공간을 만들기 

 

 

 

내가 막혔던 부분

 

- DFS 알고리즘을 구상하는 방법

- 양이 무리를 이루는 규칙 찾기

   (ex) 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들

- 재귀 호출에 대한 기본적인 개념

 

 

 

문제 풀이 방법

 

(1) 테스트 케이스의 수를 입력 받기

 

(2) 그리드의 높이(H)와 너비(W) 입력 받기

 

(3) 양과 풀의 정보를 저장할 수 있는 배열(graph) 선언하기

 

(4) 이중 for 문을 사용하여 높이(H)와 너비(W) 값을 이중 리스트 인덱스로 사용하기

 

(5) 인덱스에 해당하는 위치에 '#'이 존재한다면 dfs 함수 호출하기

 

(6) dfs 알고리즘을 사용하기

     - 이미 방문한 곳은 '.' (풀)로 바꾸기

     - 상하좌우에 또 '#'이 존재하는지 확인한 후, 존재한다면 다시 dfs 함수 호출 or 존재하지 않는다면 반복 루프 벗어나기

     - 더 이상의 양 무리를 셀 수 없을 때까지 반복하기(연속으로 붙어있는 #이 더 이상 존재하지 않을 때 <= 이미 방문한 노         드는 '.'으로 바뀌기 때문)

 

(7) dfs 함수를 빠져나왔다면 count 변수에 +1 하기

 

(8) (4) ~ (7) 반복한 후 최종 count 값 출력하기

 

(9) (1) 에서 입력 받았던 테스트 케이스 수만큼 (2) ~ (8) 과정 반복하기

 

 

 

소스코드

import sys
sys.setrecursionlimit(100000)

T = int(input())        # 입력 받을 테스트 케이스의 수

""" dfs 알고리즘 사용 하기 """
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 < H and nx < W:   # 지정 범위를 벗어 나지 않는 선에서 확인 하기
            if graph[ny][nx] == '#':    # '#'을 발견했으면 다시 그 자리에서 재귀 호출
                dfs(ny, nx)

for _ in range(T):
    H,W = map(int, input().split())     # 그리드의 높이(H)와 너비(W) 입력받기
    graph = [list(input()) for _ in range(H)]   # 양과 풀의 그리드 정보를 저장할 수 있는 공간 설정
    count = 0   # 몇 개의 양 무리가 있는지 카운트 할 변수
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':  # 양이 발견 됐을 경우
                dfs(i, j)
                count += 1  # 하나의 무리 발견 (카운트 추가)

    print(count)