[Python] BOJ 3184 - 양(ovce)

www.acmicpc.net/problem/3184

3184번: 양

전형적인 그래프 탐색문제이다.

 

1. m에 마당을 입력받고 마당칸 만큼 visited배열을 만들어주고 False를 넣어준다.

 

2. bfs함수: sheep, wolf = 0, 0으로 설정하고 bfs를 돌려준다. q에서 x, y원소를 뽑고 m[x][y]가 o라면 sheep 1증가, v라면 wolf를 1증가시키고 m[x][y]를 #으로 변경

 

3. 상하좌우 방향을 탐색하며 좌표 밖을 벗어나지 않고 m[nx][ny]가 #이 아니고 (nx, ny)를 방문하지 않았다면 방문처리를 해주고 q에 넣어준다.

 

4. bfs를 다 돌고 나서 양의 수가 늑대의 수보다 많으면(sheep > wolf) 늑대를 없애주고 아니면 양을 0으로 만들어준다.

 

5. (출력) 반복문을 돌며 m[i][j]가 o 또는 v 일때 bfs(i, j)를 수행해 각각의 울타리마다 늑대와 양의 수를 더해주고 마지막에 출력해준다.

 

from collections import deque
import sys
input = sys.stdin.readline
R, C = map(int,input().split())
m = [list(input().rstrip()) for _ in range(R)]
visited = [[False] * C for _ in range(R)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x, y):
	sheep, wolf = 0, 0
	q = deque()
	q.append([x, y])
	while q:
		x, y = q.popleft()
		if m[x][y] == 'o':
			sheep += 1
		if m[x][y] == 'v':
			wolf += 1
		m[x][y] = '#'
		for i in range(4):
			nx, ny = x + dx[i], y + dy[i]
			if 0 <= nx < R and 0 <= ny < C and m[nx][ny] != '#' and not visited[nx][ny]:
				visited[nx][ny] = True
				q.append([nx, ny])
	if sheep > wolf:
		wolf = 0
	else:
		sheep = 0
	return sheep, wolf
		
sheep_cnt, wolf_cnt = 0, 0
for i in range(R):
	for j in range(C):
		if m[i][j] == 'o' or m[i][j] == 'v':
			sheep, wolf = bfs(i, j)
			sheep_cnt += sheep
			wolf_cnt += wolf
print(sheep_cnt, wolf_cnt)