[BOJ] 3184 양

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

문제요약

• 마당은 평지(.), 울타리(#), 늑대(v), 양(o)으로 구분된다.
• 양과 늑대는 울타리를 넘을 수 없으며, 울타리에 둘러싸인 영역은 같은 영역이다.
• 같은 영역 내에 늑대 수>=양의 수인 경우 늑대가 모두 양을 잡아먹고, 그 반대인 경우 양이 이긴다.(문제에서 양이 이긴다라고 되어 있지만 늑대가 죽어서 없어지는 것으로 이해해야함)
• 위와 같은 조건일 때 다음날 살아남은 양과 늑대의 수를 출력한다.

접근

• 재귀로 인접한 지역을 탐색하여 같은 영역에 존재하는 늑대와 양의 수를 카운트한다.
• 양 또는 늑대의 사방이 울타리로 둘러싸인 경우 인접한 영역이 존재하지 않으므로 재귀가 아닌 이중 for문 index를 통해 접근하여 카운트한다.
• bool 형태의 2차원 리스트를 만들어 중복 탐색을 방지한다.

코드

import sys
sys.setrecursionlimit(10**8)
def is_inside_yard(y,x): # 탐색하려는 영역이 유효한지 확인 
    if y>=0 and y<r and x>=0 and x<c:
        if yard[y][x]!='#':
            return True
    return False

def check_yard(y,x): # 같은 영역 내에 있는 늑대와 양의 수를 체크
    visited[y][x]=True
    if yard[y][x]=='v':
        global wolf
        wolf=wolf+1
    elif yard[y][x]=='o':
        global sheep
        sheep=sheep+1

    for i in control: # 상하좌우 탐색
        _y=y+i[0]
        _x=x+i[1]
        if is_inside_yard(_y,_x) and visited[_y][_x]==False:
            check_yard(_y,_x)
    
control=((-1,0),(1,0),(0,-1),(0,1))
r,c=map(int,input().split())
yard=[sys.stdin.readline() for _ in range(r)]
visited=[[False]*c for _ in range(r)]
live_wolf,live_sheep=0,0

for i in range(r): 
    for j in range(c):
        if yard[i][j]!='#' and visited[i][j]==False:
            wolf,sheep=0,0
            check_yard(i,j)
            if wolf>=sheep:
                live_wolf+=wolf
            else:
                live_sheep+=sheep
print(live_sheep,live_wolf)