[백준] 3184 - 양

1. 문제

3184번: 양

2. 개요

마당에 빈 공간, 울타리, 양, 늑대가 있다.

울타리로 둘러싸인 공간을 영역이라고 한다.

영역 내에 늑대보다 양이 많다면 늑대가 사라지고, 그렇지 않다면 양이 사라진다.

남아있는 양과 늑대를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음 입력받을 때 양의 수와 늑대의 수를 모두 구해둔다.

방문하지 않은 영역마다 BFS로 탐색하면서 방문처리를 하고 양과 늑대를 카운팅한다.

영역 내의 양과 늑대의 수를 비교하면서 양이 더 많다면 영역 내의 늑대 수 만큼 늑대를 빼주고,

그렇지 않다면 영역 내의 양의 수 만큼 양을 빼준다.

모든 영역에 대한 탐색을 마쳤다면 양과 늑대의 수를 출력한다.

3-2. Python

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

board = []

visited = [[False for i in range(C)] for j in range(R)]

sheeps = 0
wolves = 0

for i in range(R):
    board.append(list(sys.stdin.readline().rstrip()))

    for j in range(C):
        if board[i][j] == 'v':
            wolves += 1

        elif board[i][j] == 'o':
            sheeps += 1

def bfs(y, x):
    global sheeps
    global wolves

    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    scount, wcount = 0, 0

    q = deque([[y, x]])

    while q:
        now = q.popleft()
        nowY, nowX = now[0], now[1]

        for i in range(4):
            nextY, nextX = nowY + dirY[i], nowX + dirX[i]

            if nextY < 0 or nextY >= R or nextX < 0 or nextX >= C:
                continue

            if board[nextY][nextX] == '#':
                continue

            if visited[nextY][nextX] == True:
                continue

            if board[nextY][nextX] == 'o':
                scount += 1

            elif board[nextY][nextX] == 'v':
                wcount += 1

            visited[nextY][nextX] = True
            q.append([nextY, nextX])

    if scount > wcount:
        wolves -= wcount

    else:
        sheeps -= scount

for i in range(R):
    for j in range(C):
        if visited[i][j] == False and board[i][j] != '#':
            visited[i][j] == True
            bfs(i, j)
print(sheeps, wolves)

3-3. C#

namespace boj_3184
{
    internal class Program
    {
        static bool[,] visited;
        static char[,] board;
        static int sheep;
        static int wolves;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int R = int.Parse(input[0]);
            int C = int.Parse(input[1]);

            sheep = 0;
            wolves = 0;

            visited = new bool[R, C];
            board = new char[R, C];

            for (int i = 0; i < R; i++)
            {
                string row = sr.ReadLine();

                for (int j = 0; j < C; j++)
                {
                    board[i, j] = row[j];

                    if (board[i, j] == 'o')
                        sheep++;

                    else if (board[i, j] == 'v')
                        wolves++;
                }
            }

            for (int i = 0; i < R; i++)
            {
                for (int j = 0; j < C; j++)
                {
                    if (!visited[i, j] && board[i, j] != '#')
                    {
                        visited[i, j] = true;
                        BFS(i, j, R, C);
                    }
                }
            }

            sw.WriteLine($"{sheep} {wolves}");
            sw.Close();
        }

        static void BFS(int y, int x, int r, int c)
        {
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            int scount = 0;
            int wcount = 0;

            if (board[y, x] == 'o')
                scount++;

            else if (board[y, x] == 'v')
                wcount++;

            Queue<int[]> q = new Queue<int[]>();

            q.Enqueue(new int[] { y, x });

            while (q.Count > 0)
            {
                int[] now = q.Dequeue();
                int nowY = now[0];
                int nowX = now[1];

                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + dirY[i];
                    int nextX = nowX + dirX[i];

                    if (nextY < 0 || nextY >= r || nextX < 0 || nextX >= c)
                        continue;

                    if (visited[nextY, nextX])
                        continue;

                    if (board[nextY, nextX] == '#')
                        continue;

                    if (board[nextY, nextX] == 'o')
                        scount++;

                    else if (board[nextY, nextX] == 'v')
                        wcount++;

                    visited[nextY, nextX] = true;
                    q.Enqueue(new int[] { nextY, nextX });
                }
            }

            if (scount > wcount)
                wolves -= wcount;

            else
                sheep -= scount;
        }
    }
}