[파이썬] 백준 3184 : 양

[파이썬] 백준 3184 : 양

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

3184번: 양

실버 2

그래프, DFS, BFS

---

접근

울타리의 경계를 만날 때까지 영역 내의 다른 좌표들을 탐색해야 하므로 bfs가 적합하다.

좌표를 움직이되, 설정한 경계값을 넘지 않았는지, 방문하지 않았는지, 해당 좌표에 울타리가 존재하지 않는지 확인하고 만약 늑대가 있다면 늑대의 수를, 양이 있다면 양의 수를 더해준다.

bfs의 탐색이 끝나는 경우는 울타리 내의 모든 영역에 대한 탐색이 끝나는 경우이므로, 늑대와 양의 수를 비교하여 양의 수가 더 많은 경우에만 양이 생존할 수 있도록 값을 조정해야 한다.

 

지금까지 BFS를 구현할때는 그래프의 정점에 대한 값을 큐에 넣었는데, 좌표값 자체를 넣고 빼는 방법도 있다는 것을 알게 되었다.

 

from collections import deque
x, y = 1, 2
queue = deque()
queue.append([x, y])
print(queue)
nx, ny = queue.popleft()
print(nx, ny)

이 방법을 응용하면 좌표값 각각을 큐에서 빼낼 수 있으므로 좌표 이동을 표현할 때 용이하다.

 

코드

import sys; input = sys.stdin.readline
from collections import deque

v, o = 0, 0

def bfs(x, y):
    global v
    global o
    queue = deque()
    queue.append([x, y])
    visited[x][y] = 1
    v_cnt, o_cnt = 0, 0
    if field[x][y] == 'v':
        v_cnt += 1
    if field[x][y] == 'o':
        o_cnt += 1
        
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            ndx = x + dx[i]
            ndy = y + dy[i]
            if 0 <= ndx < R and 0 <= ndy < C and visited[ndx][ndy] == 0 and field[ndx][ndy] != '#':
                if field[ndx][ndy] == 'v':
                    v_cnt += 1
                if field[ndx][ndy] == 'o':
                    o_cnt += 1
                queue.append([ndx, ndy])
                visited[ndx][ndy] = 1
    if v_cnt < o_cnt:  # 수가 작은 쪽의 동물의 수를 기존에 입력하면서 초기화 했던 동물의 수에다가 뺀다.
        v -= v_cnt
    else:
        o -= o_cnt
        

R, C = map(int, input().split())
visited = [[0]*C for _ in range(R)]
field = []
for i in range(R):
    f = list(input().strip())
    for j in range(C):  # 입력값을 주면서 늑대와 양의 개수를 변수에 초기화한다.
        if f[j] == 'o':
            o += 1
        if f[j] == 'v':
            v += 1
    field.append(f)
        

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(R):
    for j in range(C):
        if (field[i][j] == 'o' or field[i][j] == 'v') and visited[i][j] == 0:
            bfs(i, j)
print(o, v)