BOJ3184 : 양 (Silver 1)

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

오랜만에 돌아온 PS~~~^~^

여러분 혹시 한 번에 맞은 기분이 어떤지 아시나요

일단 저는 압니다

ㅎ히히ㅣ히히 

지금 당연히 뭐하나 예외 있겠지 하고 냅다 돌려봤는데 갑자기 100% 뜨고 맞았습니다 떠서 소리지를뻔함

 

정말 오랜만에 백준 다시 풀고 있는데 어째서인지 한참 공부할 때보다 머리가 더 팽팽 잘 돌아가유,,,

옛날엔 실버 1 이렇게 빨리 못 풀었었는데...

 

그럼 설명을 해보겠습니당

 

 

 

1. 우선 기호를 전부 숫자로 바꿔 이차원 배열 map에 저장해준다

 

보자마자 왜인지 기호 그대로 냅두면 내가 너무 헷갈릴 것 같아서 그냥 싹 다 숫자로 변형해서 저장해주었습니다

사실 뭐 실행 속도에 엄청 큰 제약이 있는 그런 문제였으면 굳이 안하는게 더 이득일 것 같기도 한데,, 그냥 나는 이렇게 해씀

안해도 되긴 할 것 같습니다용

 

2. count라는 함수를 호출해준다

이 때, 걍 finalnum (최종 결과값) 이라는 2차원 배열을 만들어서 포인터로 받아, 함수 안에서 배열에 직접 접근하도록 하였다. finalnum[0] = sheep num, finalnum[1] = wolf num

return 값이 두 개여야 하는 것을 생각하기 귀찮았기 때문 ㅎ

 

count 함수의 실행이 종료되면 finalnum 배열에 최종 양의 수와 늑대의 수가 업데이트 되어있으므로 이걸 그대로 출력해준다.

 

 

3. count 함수

 

좌표 (0,0)부터 (R-1, C-1)까지 하나씩 시작점을 잡아 dfs를 돈다

이 때, 왜 이렇게 했냐면, 울타리로 막혀있는 한 영역을 다 돌면 DFS가 끝나도록 설계했기 때문에, 또 다른 영역의 시작점이 어디일 지 모르기 때문! 단, 이미 본 영역을 다시 보지 않기 위해 check 값이 0일 때만 돌도록 한다.

 

main 과 마찬가지로 sheepwolf라는 2차원 배열을 만들어, 이 배열에 해당 영역에 있었던 양의 수와 늑대의 수가 저장된다.

만약 어떤 영역에 늑대보다 양이 많다면, 그 양의 수만큼 finalnum[0] 을 증가시켜주고, 늑대의 수는 증가시키지 않는다

반대로 늑대가 양보다 많거나 같다면, 그 늑대의 수만큼 finalnum[1]을 증가시켜 준다

 

이런식으로 map 전체를 한 바퀴 다 돈 다음에 함수 끝!

아 참, dfs 한 번 끝나면 sheepwolf 배열 초기화 해주는거 잊지 말기~~ (실제로 안했다가 괴상한 결과를 봄)

 

 

4. DFS 함수

 

기본적인 dfs 함수이다

일단 방문 했던 좌표이거나, 울타리면 return 해서 뒤로 back해주고

아니라면 방문 했다는 표시 해주기~ check[x][y] = 1 해주기~

 

그리고 지금 있는 좌표가 양이면 양 수 증가, 늑대면 늑대 수 증가 해주고

 

그리고 나서 이제 상하좌우로 이동해본다

이 때, 범위 벗어나지 않게 해주기!

 

영역을 세는 문제의 경우 우측, 아래로만 가는게 아니라 무조건 위랑 좌측도 탐색해봐야한다

어디가 뚫려있을지 모르게 때무네 

한 번 돌 때 영역 전체를 다 돌아야 머리 아픈 일을 막을 수 있다

 

그래서 결론적으로 DFS를 한 번 돌 때마다, 울타리 안에 있는 영역  하나를 전부 돌고, 그 영역을 check 표시 해준 다음, 양의 수와 늑대의 수를 세서 count 함수로 전달해준다.

 

 

#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

#define MAX 250
#define MIN 3


int map[MAX][MAX] = {0,};
int check[MAX][MAX] = {0,};
int R, C =0;

void count(int* finalnum);
void DFS(int x, int y, int* sheepwolf);

/*
. = 비어있는 field = 0
# = 울타리 = 1
o = 양 = 2
v = 늑대 = 3
*/ 

int main(){
   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int i, j =0;

    cin >> R >> C;

    for(i=0;i<R; i++){
        for(j=0; j<C; j++){
            char tmp;
            cin >> tmp;
            if (tmp == '.')
                map[i][j] = 0;
            else if (tmp == '#')
                map[i][j] = 1;
            else if (tmp == 'o')
                map[i][j] = 2;
            else if (tmp == 'v')
                map[i][j] = 3;

        }
    }
    int n, m  = 0;

    // cout <<"map------\n" ;
    // for(n=0; n<R; n++){
    //     for(m=0;m<C;m++){
    //         cout << map[n][m]<<" ";
    //     }
    //     cout <<"\n";
    // }

    // cout <<"\n";
    int finalnum[2]= {0,0};
    count(finalnum);
    cout << finalnum[0] << " " << finalnum[1];

}

void count(int* finalnum){
    int i, j=0;
    int n, m=0;
    int sheepwolf[2] = {0,0}; //{양의 수, 늑대수}

    for(i=0; i<R; i++){
        for(j=0; j<C; j++){
            if(check[i][j]==0){
                DFS(i, j, sheepwolf);

                // cout << "check ------\n";
                // for(n=0; n<R; n++){
                //     for(m=0;m<C;m++){
                //         cout<<check[n][m]<<" ";
                //     }
                //     cout <<"\n";
                // }
                // cout <<"\n";

                if(sheepwolf[0]>sheepwolf[1]){
                    finalnum[0] += sheepwolf[0];
                }
                else {
                    finalnum[1] += sheepwolf[1];
                }
                sheepwolf[0] = 0 ; sheepwolf[1] = 0;
            }
        }
    }

}



void DFS (int x, int y, int* sheepwolf){
    if(check[x][y] == 1 || map[x][y] == 1)
        return;
    if (map[x][y] == 2) sheepwolf[0] ++;
    if (map[x][y]==3) sheepwolf[1] ++;

    check[x][y] = 1;

    if(x>0) DFS(x-1, y, sheepwolf);
    if(y>0) DFS(x, y-1, sheepwolf);
    if(x<R-1) DFS(x+1,y, sheepwolf);
    if(y<C-1) DFS(x,y+1, sheepwolf);

}

 

그리고 깔끔하게 1트만에 맞았음

행복해라.....이제 골드로 도전해볼게용