[ baekjoon ] 양 3184번, 양치기 꿍 3187번 ( python )

문제

백준 3184 양 풀이 ( 파이썬 )

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

 

백준 3187 양치기 꿍 풀이 ( 파이썬 )

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

 

 

풀이

일단 3184번과 3187번은 그냥 문제가 똑같았다. 양이 o인지 k인지만 바꿔주면 된다.

먼저 양의 좌표와 늑대의 좌표를 따로 저장해 놓고 방문 체크를 하면서 같은 우리에 있다면 양인지 늑대인지 판별하고 마리 수를 세준다.

bfs 함수 안에 들어가면 먼저 이미 셌는지 확인하고 셌다면 바로 리턴, 아니면 bfs로 우리 안을 확인하고 양과 늑대 수를 리턴한다.

늑대와 양 따로 해준 이유는 울타리 안에 한 종류만 있을 수 있기 때문.

 

• 3184 풀이

from collections import deque

r,c=map(int,input().split())

arr=[]

visited=[[False]*c for _ in range(r)]

sheep=[]
wolf=[]

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

for i in range(r):
    arr.append(list(input()))
    for j in range(c):
        if arr[i][j]=='o':
            sheep.append((i,j))
        if arr[i][j]=='v':
            wolf.append((i,j))

def bfs(x,y,ns,nw):
    if visited[x][y]==True:
        return [0,0]
    
    visited[x][y]=True
    q=deque()
    q.append((x,y))


    while q:
        x,y=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:
                continue
            if arr[nx][ny]=='#' or visited[nx][ny]==True:
                continue
            visited[nx][ny]=True
            if arr[nx][ny]=='v':
                nw+=1
            if arr[nx][ny]=='o':
                ns+=1
            q.append((nx,ny))
    
    return [ns,nw]

ts=0
tw=0

for i in range(len(sheep)):
    x,y=sheep[i]
    temp=bfs(x,y,1,0)
    if temp[0]>temp[1]:
        ts+=temp[0]
    else:
        tw+=temp[1]

for i in range(len(wolf)):
    x,y=wolf[i]
    temp=bfs(x,y,0,1)
    if temp[0]>temp[1]:
        ts+=temp[0]
    else:
        tw+=temp[1]

print(ts,tw)

 

• 3187 풀이

from collections import deque

r,c=map(int,input().split())

arr=[]

visited=[[False]*c for _ in range(r)]

sheep=[]
wolf=[]

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

for i in range(r):
    arr.append(list(input()))
    for j in range(c):
        if arr[i][j]=='k':
            sheep.append((i,j))
        if arr[i][j]=='v':
            wolf.append((i,j))

def bfs(x,y,ns,nw):
    if visited[x][y]==True:
        return [0,0]
    
    visited[x][y]=True
    q=deque()
    q.append((x,y))


    while q:
        x,y=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:
                continue
            if arr[nx][ny]=='#' or visited[nx][ny]==True:
                continue
            visited[nx][ny]=True
            if arr[nx][ny]=='v':
                nw+=1
            if arr[nx][ny]=='k':
                ns+=1
            q.append((nx,ny))
    
    return [ns,nw]

ts=0
tw=0

for i in range(len(sheep)):
    x,y=sheep[i]
    temp=bfs(x,y,1,0)
    if temp[0]>temp[1]:
        ts+=temp[0]
    else:
        tw+=temp[1]

for i in range(len(wolf)):
    x,y=wolf[i]
    temp=bfs(x,y,0,1)
    if temp[0]>temp[1]:
        ts+=temp[0]
    else:
        tw+=temp[1]

print(ts,tw)