백준 3184 양 C++

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

 

3184번: 양

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ3184_dfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ3184
//
//  Created by Hwayeon on 2021/08/24.
//

#include <iostream>
#include <vector>
using namespace std;

int R, C;
char yard[250][250] = {'.',};
int visit[250][250] = {0,};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
vector<pair<int, int>> wolf, sheep;
int sheeps = 0;
int wolves = 0;

void dfs(int x, int y){
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=C || ny<0 || ny>=R) continue;
        if(visit[ny][nx] == 1) continue;
        if(yard[ny][nx] == '#') continue;
        else if(yard[ny][nx] == 'v'){
            wolf.push_back({nx, ny});
        }
        else if(yard[ny][nx] == 'o'){
            sheep.push_back({nx, ny});
        }
        visit[ny][nx] = 1;
        dfs(nx, ny);
    }
}

int main(int argc, const char * argv[]) {
    cin >> R >> C;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> yard[i][j];
        }
    }
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(yard[i][j] != '#' && visit[i][j] == 0){
                wolf.clear();
                sheep.clear();
                visit[i][j] = 1;
                if(yard[i][j] == 'v') wolf.push_back({j, i});
                else if(yard[i][j] == 'o') sheep.push_back({j, i});
                dfs(j, i);
                if(wolf.size() < sheep.size()){
                    sheeps += sheep.size();
                }
                else{
                    wolves += wolf.size();
                }
            }
        }
    }
    cout << sheeps << " " << wolves << endl;
    return 0;
}

 

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ3184_bfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ3184_bfs
//
//  Created by Hwayeon on 2021/08/24.
//

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int R, C;
char yard[250][250] = {'.',};
int visit[250][250] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
vector<pair<int, int>> wolf, sheep;
int wolves = 0;
int sheeps = 0;

void bfs(int sx, int sy){
    wolf.clear();
    sheep.clear();
    visit[sy][sx] = 1;
    if(yard[sy][sx] == 'v') wolf.push_back({sx, sy});
    else if(yard[sy][sx] == 'o') sheep.push_back({sx, sy});
    queue<pair<int, int>> q;
    q.push({sx, sy});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx<0 || nx>=C || ny<0 || ny>=R) continue;
            if(visit[ny][nx] == 1) continue;
            if(yard[ny][nx] == '#') continue;
            else if(yard[ny][nx] == 'v') wolf.push_back({nx, ny});
            else if(yard[ny][nx] == 'o') sheep.push_back({nx, ny});
            q.push({nx, ny});
            visit[ny][nx] = 1;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> R >> C;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> yard[i][j];
        }
    }
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(yard[i][j]!='#' && visit[i][j]==0){
                bfs(j, i);
                if(sheep.size() > wolf.size()) sheeps += sheep.size();
                else wolves += wolf.size();
            }
        }
    }
    cout << sheeps << " " << wolves << endl;
    return 0;
}

---

풀이 과정

1. DFS

풀이 시간 30분

 

 

#include <iostream>
#include <vector>
using namespace std;

int R, C;
char yard[250][250] = {'.',};

//탐색한 영역 방문 표시를 위한 배열
int visit[250][250] = {0,};

//0-좌, 1-상, 2-우, 3-하
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//특정 지역의 늑대와 양의 위치를 담는 벡터
vector<pair<int, int>> wolf, sheep;

//살아남은 양의 수, 늑대의 수
int sheeps = 0;
int wolves = 0;

void dfs(int x, int y){
	//현재 위치를 기준으로 인접한 네 방향 탐색
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        //범위를 벗어나는 경우 무시한다
        if(nx<0 || nx>=C || ny<0 || ny>=R) continue;
        //이미 방문한 위치라면 무시한다
        if(visit[ny][nx] == 1) continue;
        
        //인접한 위치가 울타리인 경우 무시한다
        if(yard[ny][nx] == '#') continue;
        //인접한 위치에 늑대가 있는 경우, wolf 벡터에 추가한다
        else if(yard[ny][nx] == 'v'){
            wolf.push_back({nx, ny});
        }
		//인접한 위치에 양이 있는 경우, sheep 벡터에 추가한다
        else if(yard[ny][nx] == 'o'){
            sheep.push_back({nx, ny});
        }
        //인접 위치를 방문처리하고, 인접 위치를 기준으로 dfs를 실행한다
        //인접 위치가 빈 칸이거나, 양이 있거나, 늑대가 있는 경우 실행
        visit[ny][nx] = 1;
        dfs(nx, ny);
    }
}

int main(int argc, const char * argv[]) {
    cin >> R >> C;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> yard[i][j];
        }
    }
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
        	//현재 위치가 울타리가 아니면서 방문하지 않은 지역인 경우, 해당 위치를 기준으로 dfs를 진행한다
            if(yard[i][j] != '#' && visit[i][j] == 0){
            	//해당 지역의 늑대와 양을 담을 벡터를 초기화
                wolf.clear();
                sheep.clear();
                
                //해당 위치를 방문 처리
                visit[i][j] = 1;
                
                //해당 위치에 늑대가 있는 경우, wolf 벡터에 추가
                if(yard[i][j] == 'v') wolf.push_back({j, i});
                //해당 위치에 양이 있는 경우, sheep 벡터에 추가
                else if(yard[i][j] == 'o') sheep.push_back({j, i});
                
                //해당 위치를 시작으로 dfs 진행
                dfs(j, i);
                
                //해당 지역의 늑대의 수가 양의 수보다 적은 경우, 양은 모두 살아남으므로 양의 수 카운팅
                if(wolf.size() < sheep.size()){
                    sheeps += sheep.size();
                }
                //해당 지역의 늑대의 수가 양의 수보다 많거나 같은 경우, 늑대가 양을 모두 잡아먹으므로 늑대의 수 카운팅
                else{
                    wolves += wolf.size();
                }
            }
        }
    }
    cout << sheeps << " " << wolves << endl;
    return 0;
}
//시간복잡도 = O(V(V+E)) = O(V^2), 공간복잡도 = O(V)

 

2. BFS

풀이 시간 12분

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int R, C;
char yard[250][250] = {'.',};
//특정 위치의 방문 여부를 표시하기 위한 배열
int visit[250][250] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//특정 지역의 늑대와 양의 위치를 담는 벡터
vector<pair<int, int>> wolf, sheep;

//살아남은 양의 수, 늑대의 수
int wolves = 0;
int sheeps = 0;

void bfs(int sx, int sy){
    //해당 지역의 늑대와 양을 담을 벡터를 초기화
    wolf.clear();
    sheep.clear();
    //시작 위치를 방문 처리
    visit[sy][sx] = 1;
    
    //시작 위치에 양이 있는 경우, sheep 벡터에 추가
    if(yard[sy][sx] == 'v') wolf.push_back({sx, sy});
    //시작 위치에 늑대가 있는 경우, wolf 벡터에 추가한다
    else if(yard[sy][sx] == 'o') sheep.push_back({sx, sy});
    queue<pair<int, int>> q;
    q.push({sx, sy});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        //현재 위치를 기준으로 인접한 네 방향 탐색
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            //범위를 벗어나는 경우 무시한다
            if(nx<0 || nx>=C || ny<0 || ny>=R) continue;
            //인접한 위치를 이미 방문한 경우 무시한다
            if(visit[ny][nx] == 1) continue;
            //인접한 위치가 울타리인 경우 무시한다
            if(yard[ny][nx] == '#') continue;
            
            //인접한 위치에 늑대가 있는 경우, wolf 벡터에 추가한다
            else if(yard[ny][nx] == 'v') wolf.push_back({nx, ny});
            //인접한 위치에 양이 있는 경우, sheep 벡터에 추가
            else if(yard[ny][nx] == 'o') sheep.push_back({nx, ny});
            
            //해당 위치를 기준으로 bfs가 실행되도록 q에 push하고 방문 처리한다
            //인접 위치가 빈 칸이거나, 양이 있거나, 늑대가 있는 경우 실행
            q.push({nx, ny});
            visit[ny][nx] = 1;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> R >> C;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> yard[i][j];
        }
    }
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            //현재 위치가 울타리가 아니면서 방문하지 않은 지역인 경우, 해당 위치를 기준으로 bfs를 시작한다
            if(yard[i][j]!='#' && visit[i][j]==0){
                bfs(j, i);
                //해당 지역의 늑대의 수가 양의 수보다 적은 경우, 양은 모두 살아남으므로 양의 수 카운팅
                if(sheep.size() > wolf.size()) sheeps += sheep.size();
                //해당 지역의 늑대의 수가 양의 수보다 많거나 같은 경우, 늑대가 양을 모두 잡아먹으므로 늑대의 수 카운팅
                else wolves += wolf.size();
            }
        }
    }
    cout << sheeps << " " << wolves << endl;
    return 0;
}
//시간복잡도 = O(V(V+E)) = O(V^2), 공간복잡도 = O(V)