[백준] 3184 - 양

1. 문제

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

3184번: 양

 

2. 접근

1. 울타리로 가둬져있는 각각의 공간마다 wolf, sheep 수를 구해준다.

2. 한 지점부터 dfs로 상하좌우로 재귀함수를 실행한다

3. dfs 의 x,y 지점이 True라면 4번으로 진행한다 

4. 각 영역마다의 wolf >= sheep 이면 w += wolf , wolf < sheep 이면 s += sheep를 해준다

 

3. 풀이

# 3184 실버1
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())

board = []
for i in range(n):
    board.append(list(map(str,input().rstrip())))

wolf, sheep = 0,0
w,s = 0,0

visited = [[False] * m for _ in range(n)]

def dfs(x,y):
    global wolf, sheep
    if 0<=x<n and 0<=y<m and visited[x][y] == False:
        if board[x][y] != '#':
            visited[x][y] = True
            if board[x][y] == 'o':
                sheep += 1
            elif board[x][y] == 'v':
                wolf += 1
            dfs(x-1,y)
            dfs(x+1,y)
            dfs(x,y-1)
            dfs(x,y+1)
            return True
    return False

for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            if sheep > wolf:
                s += sheep
            else:
                w += wolf
            sheep , wolf = 0,0
print(s,w)