BOJ 3184 양

저와 스터디하는 민지군이 고른 문제입니다. 요즘 민지군이 그래프에 빠진거 같아요. 근데 저도 그래프 문제를 좋아해서 아주 굿입니다.

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

풀이 방법

간단한 그래프 탐색 문제입니다. BFS로 풀었으며, 생각을 조금 해야할 것은
1.어느 지점에서 그래프 탐색을 돌릴 것인가
2.양과 늑대의 수는 어떻게 수합할 것인가
이 두가지를 따져보고 풀면 쉽게 풀 수 있을거란 생각이 들었습니다.

코드

def bfs(i,j):

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    d = deque()
    visited[i][j] = 1
    d.append([i,j])
    cnt_s,cnt_w = 0,0

    if arr[i][j] == 'v':
        cnt_w += 1
    elif arr[i][j] == 'o':
        cnt_s +=1 

    while d:
        x,y = d.popleft()
        for i in range(4):
            a,b = x+dx[i],y+dy[i]
            if 0<=a<N and 0<=b<M and not visited[a][b] and arr[a][b] != '#':
                visited[a][b] = 1
                if arr[a][b] == 'o':
                    cnt_s += 1
                elif arr[a][b] == 'v':
                    cnt_w += 1

                d.append([a,b])

    if cnt_s>cnt_w:
        return cnt_s,0
    else:
        return 0,cnt_w



import sys
input = sys.stdin.readline 
from collections import deque
N,M = map(int,input().split())

arr = [list(input().strip()) for _ in range(N)]

visited = [[0]*M for _ in range(N)]

sheep,wolf = 0,0

for i in range(N):
    for j in range(M):
        if arr[i][j] != '#' and not visited[i][j]:
            # print(i,j)
            sheep_cnt,wolf_cnt = bfs(i,j)
            # print(sheep_cnt,wolf_cnt)
            sheep+=sheep_cnt
            wolf+=wolf_cnt

print(sheep,wolf)