[bfs/백준] 3184번 : 양

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

 

Silver Level1 문제 

방문하지 않았고, 울타리가 아닌 지역을 중심으로 영역을 진행한다. 

이때 v의 갯수와 o의 갯수를 센 다음 크기 비교를 통해 늑대 또는 양의 수를 누적해간다

 

그런데 시작 지점이 ' . ' 이 아닌 'v' 또는 'o'인 경우 이걸 세는 로직이 아니었어서 계속 7%에서 계속 틀렸다

그래서 탐색 시작시 v인지 o인지 확인하는 로직을 추가한 후 돌렸더니 정답이 떴다

visit[x][y]=1
    if data[x][y]=='o':
        result[0]+=1
    elif data[x][y]=='v':
        result[1]+=1

 

- 정답 풀이 :

from collections import deque

r,c=map(int,input().split())
data=[]
for _ in range(r):
    data.append(list(input()))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*c for _ in range(r)]

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    result=[0,0]
    visit[x][y]=1
    
    if data[x][y]=='o':
        result[0]+=1
    elif data[x][y]=='v':
        result[1]+=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 visit[nx][ny]:
                if data[nx][ny]=='.':
                    visit[nx][ny]=1
                    queue.append((nx,ny))
                elif data[nx][ny]=='v':
                    result[1]+=1
                    visit[nx][ny]=1                    
                    queue.append((nx,ny))
                elif data[nx][ny]=='o':
                    result[0]+=1
                    visit[nx][ny]=1
                    queue.append((nx,ny))
    return result

answer=[0,0]                    
for i in range(r):
    for j in range(c):
        if not visit[i][j] and data[i][j]!='#':
            result=bfs(i,j)
            #양이 다 먹히는 경우
            if result[0]<=result[1]:
                answer[1]+=result[1]
            else:
                answer[0]+=result[0]
                
print(answer[0],answer[1])

 

- 더 나은 풀이 

from collections import deque

r,c=map(int,input().split())
data=[]
for _ in range(r):
    data.append(list(input()))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*c for _ in range(r)]

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    global wolf,sheep
    visit[x][y]=1
    if data[x][y]=='v':
        wolf+=1
    elif data[x][y]=='o':
        sheep+=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 visit[nx][ny]) and (data[nx][ny]!='#'):
                if data[nx][ny]== 'o':
                    sheep+=1
                if data[nx][ny]== 'v':
                    wolf+=1
                visit[nx][ny]=1
                queue.append((nx,ny))
                    

answer=[0,0]                    
for i in range(r):
    for j in range(c):
        if not visit[i][j] and data[i][j]!='#':
            sheep,wolf=0,0
            bfs(i,j)
            #양이 다 먹는 경우
            if sheep>wolf:
                answer[0]+=sheep
            else:
                answer[1]+=wolf
                
print(answer[0],answer[1])