[파이썬/Python] 백준 11123번: 양 한마리... 양 두마리...

숨·2024년 8월 9일

코테

알고리즘 문제 풀이

목록 보기

45/105

📌 문제 : 백준 11123번

📌 문제 탐색하기

T : 테스트 케이스의 수 ( $0 < T ≤ 100$ )
H : 그리드의 높이 ( $0 < H ≤ 100$ )
W : 그리드의 너비 ( $0 < W ≤ 100$ )

✅ 입력 조건
1. T 입력
2. T번 반복해 H, W 입력
✅ 출력 조건
1. 테스트 케이스별로 양의 무리 수를 한줄에 출력

입력 받은 HxW 크기의 그리드에서 # → 양, . → 풀을 의미한다.
서로 다른 #이 붙어있다면, 즉 상하좌우에 붙어 있다면 한 무리의 양들이 있다고 표현할 수 있다.
이러한 무리들이 몇 개인지 세서 출력하는 문제이다.

전체 그리드를 2차원 배열로 정의해서 입력받은 양과 풀 정보를 저장한다.

이 2차원 배열을 돌면서 붙어 있는 양을 탐색하는 함수를 BFS로 구현한다.
1. 큐를 사용해 구현한다.
2. 함수의 입력으로 현재 위치를 받는다.
3. 방문처리를 위해 해당 위치에 저장된 #을 .으로 변경해준다.
4. 현재 위치가 방문하지 않았고 #이라면 주변을 계속 탐색한다.

전체 그리드를 돌면서 양의 위치에서 위와 같이 정의한 BFS를 실행하도록 구현한다.

가능한 시간복잡도

전체 그리드 입력 → $O(H * W)$
전체 그리드 탐색 → $O(H * W)$

최종 시간복잡도
테스트 케이스를 제외하고 시간복잡도를 생각하면 $O(H * W)$ 이 된다.
최악의 경우 $O(100 * 100) = O(10000)$ 이 되는데,
이는 1초 내에 연산이 가능하다.

알고리즘 선택

입력 받은 전체 그리드를 이중 for문으로 돌면서 BFS 수행하기

📌 코드 설계하기

BFS 구현
T 입력
T번 반복해 H, W 입력
그래프 초기화 후 입력
무리 수 카운트 변수 초기화
전체 그리드를 돌면서 양의 위치에서 BFS 실행
테스트 케이스 별 얻은 양 무리 수 저장
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 확인할 방향 정의
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]


# bfs 함수
def bfs(x, y):
    queue = deque([(x, y)])
    if graph[x][y] == '#':
        # 방문 처리
        graph[x][y] = '.'
        # 큐가 빌 때까지 반복
        while queue:
            x, y = queue.popleft()
            # 4가지 방향 탐색
            for direction in directions:
                nx, ny = x + direction[0],  y + direction[1]
                # 그리드 내에 있으면서 양의 위치라면 탐색 진행
                if 0 <= nx < H and 0 <= ny < W and graph[nx][ny] == '#':
                    # 방문 처리
                    graph[nx][ny] = '.'
                    # 큐에 넣기
                    queue.append((nx, ny))


# T 입력
T = int(input())

# 테스트 케이스 별 정답 저장 리스트
answer = []

# T번 반복
for _ in range(T):
    # H, W 입력
    H, W = map(int, input().split())
    # 그래프 초기화
    graph = []

    # H x W 크기의 그리드 입력
    for _ in range(H):
        grid = list(map(str, input().rstrip()))
        graph.append(grid)

    # 무리 수 카운트
    count = 0

    # BFS 탐색
    for i in range(H):
        for j in range(W):
            # 양이 있는 위치에서 탐색 진행
            if graph[i][j] == '#':
                bfs(i, j)
                count += 1

    # 정답 저장
    answer.append(count)

# 결과 출력
for a in answer:
    print(a)