99클럽 코테 스터디 34일차 TIL (양 한마리... 양 두마리...) - 백준

오늘은 99클럽 코테 스터디 34일차입니다.

이제 약 8일정도 남았네요.. 남은 기간 keep going입니다!

---

1. 오늘의 학습 키워드

• 그래프
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

2. 문제: 양 한마리... 양 두마리... (11123번)

• 단계: 🥈실버 2티어
• 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
• 출처: https://www.acmicpc.net/problem/11123

양 한마리... 양 두마리... 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	4110	2575	2107	64.652%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

예제 출력 1 복사

6
3

---

3. 나의 풀이

3. 나의 풀이

문제 분석

이 문제는 2D 그리드 상에서 연결된 # 문자들로 이루어진 "양 무리"의 수를 세는 문제입니다. 각 양 무리는 상하좌우로 연결된 # 문자들로 구성됩니다. 따라서 이 문제는 그래프 이론 중 연결 요소를 찾는 문제로, 그래프 탐색 알고리즘인 너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)을 사용하여 해결할 수 있습니다.

코테 스터디를 진행하면서 풀었던 비슷한 문제들은 다음과 같습니다:

• https://velog.io/@jw9603/99클럽-코테-스터디-33일차-TIL-Number-of-Good-Leaf-Nodes-Pairs-LeetCode
• https://velog.io/@jw9603/99클럽-코테-스터디-32일차-TIL-Bad-Grass-백준
• https://velog.io/@jw9603/99클럽-코테-스터디-31일차-TIL-Clear-Cold-Water-백준
• https://velog.io/@jw9603/99클럽-코테-스터디-25일차-TIL-Find-if-Path-Exists-in-Graph

접근 방법

1. 그래프 탐색:
   • 주어진 그리드를 2차원 배열로 보고, #이 나타나는 지점마다 새로운 탐색을 시작합니다.
   • 이때, 상하좌우로 연결된 #들을 모두 방문하고, 방문한 #들은 다시 방문하지 않도록 처리하여 무리를 하나로 간주합니다.
   • 탐색 방법으로는 DFS와 BFS를 사용할 수 있습니다.
2. DFS (깊이 우선 탐색):
   • DFS는 주로 재귀 또는 스택을 이용해 구현합니다.
   • 재귀 호출을 통해 연결된 모든 #을 한 번에 방문하거나, 스택을 이용해 명시적으로 구현할 수 있습니다.
3. BFS (너비 우선 탐색):
   • BFS는 큐를 이용해 구현하며, 시작점부터 가까운 노드부터 차례로 방문합니다.
   • BFS는 모든 이웃을 먼저 탐색한 후, 다음 단계로 넘어가는 방식으로 작동합니다.

코드 구현

1. DFS (스택을 이용한 구현)

DFS를 스택을 사용해 구현한 방법은 명시적으로 스택을 관리하며 탐색을 진행합니다. 이 방법은 재귀 깊이에 제한이 있는 상황에서 유용합니다.

from collections import deque

def dfs(grid, visited, x, y, H, W):
    # 상, 하, 좌, 우
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    stack = deque([(x, y)])
    visited[x][y] = True

    while stack:
        cx, cy = stack.pop()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny] and grid[nx][ny] == '#':
                visited[nx][ny] = True
                stack.append((nx, ny))

def count_sheep_groups(grid, H, W):
    visited = [[False] * W for _ in range(H)]
    cnt = 0

    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#' and not visited[h][w]:
                dfs(grid, visited, h, w, H, W)
                cnt += 1

    return cnt

# 입력 처리
T = int(input().strip())
for _ in range(T):
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]

    result = count_sheep_groups(grid, H, W)
    print(result)

2. DFS (재귀를 이용한 구현)

DFS를 재귀적으로 구현하면 코드가 간결해지지만, 재귀 깊이에 제한이 있을 수 있으므로 상황에 따라 sys.setrecursionlimit을 조정해야 할 수도 있습니다.

import sys
sys.setrecursionlimit(10**6) # 이걸 꼭 설정해야 함

def dfs_recursive(grid, visited, x, y, H, W):
    # 상, 하, 좌, 우
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited[x][y] = True

    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny] and grid[nx][ny] == '#':
            dfs_recursive(grid, visited, nx, ny, H, W)

def count_sheep_groups_dfs_recursive(grid, H, W):
    visited = [[False] * W for _ in range(H)]
    cnt = 0

    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#' and not visited[h][w]:
                dfs_recursive(grid, visited, h, w, H, W)
                cnt += 1

    return cnt

# 입력 처리
T = int(input().strip())
for _ in range(T):
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]

    result = count_sheep_groups_dfs_recursive(grid, H, W)
    print(result)

3. BFS (큐를 이용한 구현)

BFS를 큐를 이용해 구현하면, 탐색 과정에서 가까운 곳부터 순차적으로 탐색하게 됩니다.

from collections import deque

def bfs(grid, visited, x, y, H, W):
    # 상, 하, 좌, 우
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(x, y)])
    visited[x][y] = True

    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny] and grid[nx][ny] == '#':
                visited[nx][ny] = True
                queue.append((nx, ny))

def count_sheep_groups_bfs(grid, H, W):
    visited = [[False] * W for _ in range(H)]
    cnt = 0

    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#' and not visited[h][w]:
                bfs(grid, visited, h, w, H, W)
                cnt += 1

    return cnt

# 입력 처리
T = int(input().strip())
for _ in range(T):
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]

    result = count_sheep_groups_bfs(grid, H, W)
    print(result)

위의 세 가지 접근 방식은 모두 2D 그리드에서 연결된 양 무리의 수를 찾는 데 사용될 수 있습니다. 각 방법은 그래프 탐색 알고리즘의 다양한 측면을 다루며, 주어진 문제 상황에 따라 적절한 방법을 선택할 수 있습니다.

• DFS (스택): 명시적인 스택 사용으로 재귀 깊이에 대한 걱정이 없지만, 코드가 약간 복잡할 수 있습니다.
• DFS (재귀): 간결한 코드 작성이 가능하지만, 재귀 깊이에 제한이 있을 수 있습니다.
• BFS (큐): 너비 우선 탐색의 특성을 활용하여 가까운 곳부터 순차적으로 탐색합니다.

---

4. 결론

확실히 유형 반복은 중요한 것 같습니다. 하지만 완전히 내것이라고 하기에는 아직 부족한 느낌이 듭니다. 계속 발전해나가야겠죠?

이 글을 읽으시는 분들도 모두 화이팅입니다!

읽어주셔서 감사합니다.