[파이썬/Python] 백준 3184(🥈1): 양

숨·2025년 8월 12일

코테

알고리즘 문제 풀이

목록 보기

110/128

📌 문제 : 백준 3184

📌 문제 탐색하기

R, C : 마당의 행과 열 수 ( $3 ≤ R, C ≤ 250$ )

문제 풀이

울타리, 양의 위치, 늑대 위치를 의미하는 마당의 구조를 입력 받고 한 울타리 내에서 조건에 따라 살아남은 양의 수, 늑대 수를 구하는 문제이다.

동일한 울타리 내에서 탐색하기 위해 BFS를 사용하고자 한다.

해당 위치가 범위 내에 있고 울타리가 아니라면 BFS를 사용해 연결된 영역 전체를 탐색한다.
이 때 양과 늑대의 수를 함께 계산해 반환하도록 한다.

전체 마당을 돌면서 방문한 적 없고 울타리가 아닌 위치에서 BFS를 수행하도록 하여 각 영역의 양과 늑대의 수를 받는다.
조건에 따라 양이 더 크면 늑대의 수를 0으로, 그 반대의 경우엔 양의 수를 0으로 변경한다.
변경된 수의 누적합을 구해서 아침에 살아남은 양과 늑대의 수로 출력한다.

가능한 시간복잡도

전체 영역에서 BFS → $O(R*C)$

최종 시간복잡도
최악일 때 $O(R*C) = O(250^2) = O(62,500)$ 이 되는데 이는 제한시간 1초 내 충분히 수행 가능하다.

알고리즘 선택

BFS로 연결된 영역에서 양과 늑대 찾아 개수 세기
전체 마당을 돌면서 BFS 수행

📌 코드 설계하기

bfs 구현
입력 받기
전체 필드를 돌면서 bfs 실행

📌 시도 회차 수정 사항

1회차

map 함수를 사용한 부분에 자료형, input().split() 형식으로 써야 하는데 잘못 작성했다.

2회차

살아있는 양과 늑대의 수가 제대로 계산되지 않았다.
코드에 방문 확인하는 변수에 인덱스를 추가해주지 않아 해당 칸의 방문 여부를 제대로 확인하지 못했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# bfs 구현
def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1

    # 양, 늑대 수 초기화
    sheep = 0
    wolf = 0

    # 초기 점 양인지 늑대인지 확인
    if field[x][y] == 'o':
        sheep += 1
    elif field[x][y] == 'v':
        wolf += 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 범위 내 인지, 방문 여부, 울타리 여부 확인
            if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and field[nx][ny] != '#':
                queue.append((nx, ny))
                visited[nx][ny] = 1
                # 양인지 늑대인지 확인
                if field[nx][ny] == 'o':
                    sheep += 1
                elif field[nx][ny] == 'v':
                    wolf += 1

    return sheep, wolf


# 입력받기
R, C = map(int, input().split())
field = [list(input().rstrip()) for _ in range(R)]

# 수평, 수직 이동방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 방문 리스트 정의
visited = [[0] * C for _ in range(R)]

# 살아있는 양, 늑대 수 초기화
sheep_live, wolf_live = 0, 0

# 탐색
for i in range(R):
    for j in range(C):
        # 울타리도 아니고 방문한 적 없으면 탐색
        if field[i][j] != '#' and not visited[i][j]:
            sheep, wolf = bfs(i, j)

            # 누가 더 많은지 확인
            if sheep > wolf:
                wolf = 0
            else:
                sheep = 0
            # 누적합 계산
            sheep_live += sheep
            wolf_live += wolf

# 결과 출력
print(sheep_live, wolf_live)