[Boj/백준] 3187 Python

문제출처: https://www.acmicpc.net/problem/3187

3187번: 양치기 꿍

 

 

1. 문제 접근 방식

.을 기준으로 BFS를 돌리고 k를 만나면 k_count를 하나 증가시키고

v를 만나면 v_count를 하나 증가시킨 후에 0으로 바꿔준다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

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

def bfs(x,y,wolf,sheep):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0


    while queue:
        x, y = queue.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 graph[nx][ny] == 'k':
                graph[nx][ny] = 0
                queue.append((nx,ny))
                sheep+=1
            elif graph[nx][ny] == 'v':
                graph[nx][ny] = 0
                queue.append((nx,ny))
                wolf+=1
            elif graph[nx][ny] == '.':
                graph[nx][ny] = 0
                queue.append((nx,ny))

    if sheep > wolf:
        result[0] += sheep
    else:
        result[1] += wolf

r, c =map(int,sys.stdin.readline().split())

graph = []
result = [0, 0]


for i in range(r):
    graph.append(list(sys.stdin.readline().strip()))
k = 0
v = 0

for i in range(r):
    for j in range(c):
        if graph[i][j] == '.':
            bfs(i,j,0,0)
        elif graph[i][j] == 'k':
            bfs(i,j,0,1)
        elif graph[i][j] == 'v':
            bfs(i,j,1,0)
            

print(*result)

 

 

3. 결과 및 느낀점

양이나 늑대가 고립되어 있을 때에도 카운팅을 해줘야 하는데

bfs 함수 인자로 넣어주기로 했다.

.일때는 0, 0을

k일때는 0,1을

v일때는 1,0을 넣어주면서 해결했다.