백준 3184번 양

문제 링크입니다: https://www.acmicpc.net/problem/3184

재미있는 BFS(Breadth First Search) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 마당을 입력받을 때 미리 양과 늑대의 마리수를 셉니다.

2. 마당의 칸을 전부 탐색하면서 양이거나 늑대라면 BFS 함수를 호출합니다.

3. 울타리 내에 있는 영역에 양과 늑대의 수를 셉니다.

i) 양이 늑대보다 많다면 늑대가 죽습니다.

ii) 양이 늑대보다 적거나 같다면 양이 죽습니다.

4. 양과 늑대를 출력합니다.

#include <iostream>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

using namespace std;

 

const int MAX = 250;

 

int R, C;

int sheep, wolf;

string graph[MAX];

bool visited[MAX][MAX];

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

void BFS(int y, int x)

{

        int curSheep = 0, curWolf = 0;

        queue <pair<int, int>> q; //y, x

        q.push({ y, x });

        visited[y][x] = true;

        if (graph[y][x] == 'o')

                 curSheep++;

        else if (graph[y][x] == 'v')

                 curWolf++;

 

        //같은 칸 안에 있는 양과 늑대의 수를 센다

        while (!q.empty())

        {

                 int curY = q.front().first;

                 int curX = q.front().second;

                 q.pop();

 

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = curY + moveDir[i].y;

                         int nextX = curX + moveDir[i].x;

 

                         if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C && !visited[nextY][nextX] && graph[nextY][nextX] != '#')

                         {

                                 visited[nextY][nextX] = true;

                                 if (graph[nextY][nextX] == 'o')

                                          curSheep++;

                                 else if (graph[nextY][nextX] == 'v')

                                          curWolf++;

                                 q.push({nextY, nextX});

                         }

                 }

        }

        //양이 더 많으면 늑대가 죽고

        if (curSheep > curWolf)

                 wolf -= curWolf;

        //양이 적거나 같으면 양이 죽는다

        else

                 sheep -= curSheep;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> R >> C;

 

        //미리 양과 늑대 마리수 센다

        for (int i = 0; i < R; i++)

        {

                 cin >> graph[i];

                 for (int j = 0; j < C; j++)

                         if (graph[i][j] == 'o')

                                 sheep++;

                         else if (graph[i][j] == 'v')

                                 wolf++;

        }

 

        //아직 방문하지 않은 칸이고 양이나 늑대일 때 BFS 호출

        for (int i = 0; i < R; i++)

                 for (int j = 0; j < C; j++)

                         if ((graph[i][j] == 'o' || graph[i][j] == 'v') && !visited[i][j])

                                 BFS(i, j);

 

        cout << sheep << " " << wolf << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~