[백준/bfs] 3184번: 양

-문제: https://www.acmicpc.net/problem/3184

3184번: 양

쉬운 문제인데 구현할게 많았던 문제

하나의 영역을 탐색할 때 늑대의 수와 양의 수를 구한뒤 해당 영역에서 양의 수 > 늑대 수 라면 해당 영역의 늑대수 만큼 없애는 것이라고 생각해서 하나의 영역을 탐색한 수 양과 늑대의 수를 각각 반환한 뒤 그거를 비교해서 쌓는 것으로 생각했는데 계속해서 에러가 나와서 구글링을 한 뒤 다음과 같은 코드를 작성했다 

 

-정답풀이:

먼저 전체 늑대수와 전체 양의 수를 구한 뒤, 조건에 맞춰서 늑대의 수를 줄이거나, 양의 수를 줄이는 방식으로 해야한다 

처음 구한 전체 값은 지역변수로 할당해준다(global)

 

from collections import deque

def bfs(x,y):
    visit[x][y]=1
    q=deque()
    q.append((x,y))
    result=[]
    global o,v
    wolf,sheep=0,0
    if s[x][y]=='v': wolf+=1
    elif s[x][y]=='o': sheep+=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<r and 0<=ny<c and not visit[nx][ny] and s[nx][ny]!='#':
                visit[nx][ny]=1
                q.append((nx,ny))                                                      
                if s[nx][ny]=='v':                                        
                    wolf+=1
                if s[nx][ny]=='o':                   
                    sheep+=1
    if wolf and sheep:
        if sheep > wolf:
            v-=wolf
        else:
            o-=sheep 
            
r,c=map(int,input().split())
s=[]
o,v=0,0
for _ in range(r):
    a=list(input().strip())
    for j in range(c):
        if a[j]=='o': o+=1
        if a[j]=='v': v+=1
    s.append(a)                
            
visit=[[0]*(c) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(r):
    for j in range(c):
        if not visit[i][j] and s[i][j]!='#':
            bfs(i,j)
            
print(o,v)

 

-틀린풀이

from collections import deque

def bfs(x,y):
    visit[x][y]=1
    q=deque()
    q.append((x,y))
    result=[]
    wolf,sheep=0,0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<r and 0<=ny<c and not visit[nx][ny] and s[nx][ny]!='#':
                visit[nx][ny]=1
                if s[nx][ny]=='.':
                    q.append((nx,ny))                  
                if s[nx][ny]=='v':
                    q.append((nx,ny))                    
                    wolf+=1
                else:
                    q.append((nx,ny))
                    sheep+=1
    if sheep>wolf:
        wolf=0
    else: 
        sheep=0
    return result.append((sheep,wolf))                 
r,c=map(int,input().split())
s=[]
for _ in range(r):
    s.append(list(map(str,input())))
    
visit=[[0]*(c) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
ans=0
cnt=0
for i in range(r):
    for j in range(c):
        if not visit[i][j] and s[i][j]!='#':
            bfs(i,j)
            ans+=result[0]
            cnt+=result[1]
print(ans,cnt)