[BOJ] #3187 양치기 꿍

시간 제한	메모리 제한	정답 비율
1 초	128 MB	62.921%

 

3187번: 양치기 꿍

문제

양치기 꿍은 늑대들을 양이 있는 울타리 안에 마구 집어넣었다.

같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많은 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹힌다.

빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 할 때 몇 마리의 양과 늑대가 살아남을지 계산하여라. 

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

해결방안

DFS로 울타리안을 차례로 점검하여 해당 울타리 안의 양과 늑대가 몇 마리 씩 있는지 확인하고 DFS에서 빠져나올 때 해당 양과 늑대가 몇 마리였는지 비교를 하여 최종적으로 남아있는 양과 늑대가 몇 마리일지 계산한다.

메모리	시간
3236 KB	0 ms

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define F(x,y,u,p) for(int x = 0 ; x<u; x++)for(int y = 0; y<p; y++)
typedef pair<int, int> p;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, m, chk[255][255], sheep, wolf, sheep_cnt, wolf_cnt;
char arr[255][255];
void dfs(int r, int c) {
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m || chk[nr][nc] || arr[nr][nc] == '#') continue;
        if (arr[nr][nc] == 'v') wolf_cnt++;
        else if (arr[nr][nc] == 'k') sheep_cnt++;
        dfs(nr, nc);
    }
    
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    F(i, j, n, m) {
        sheep_cnt = 0, wolf_cnt = 0;
        if (!chk[i][j]) {
            dfs(i, j);
            if (sheep_cnt > wolf_cnt) {
                sheep += sheep_cnt;
            }
            else {
                wolf += wolf_cnt;
            }
        }
    }
    printf("%d %d", sheep, wolf);
    return 0;
}
 
 

 

느낀점

오랜만에 BFS를 풀다가 DFS로 풀려니 방식이 같지만 다르다고 생각했다. 현재 보고 있는 위치 이후 다음 위치로 이동을 할 때 BFS는 큐를 통해서 하고, DFS는 함수를 통해서 탐색을 한다는 것을 상기시킬 수 있었다.

이래서 문제는 꾸준히 풀어야 하나보다. 화이팅!