백준 1303 전쟁 - 전투 C++

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

1303번: 전쟁 - 전투

 

최종 코드

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

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

//
//  main.cpp
//  BJ1303
//
//  Created by Hwayeon on 2021/08/30.
//

#include <iostream>
#include <math.h>
using namespace std;

int N, M;
int blue, white = 0;
char ground[100][100] = {'W', };
int visit[100][100] = {0, };

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int army = 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>=N || ny<0 || ny>=M) continue;
        if(visit[ny][nx]) continue;
        if(ground[ny][nx] != ground[y][x]) continue;
        visit[ny][nx] = 1;
        dfs(nx, ny);
        army++;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            scanf("%1s", &ground[i][j]);
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(visit[i][j] == 0){
                visit[i][j] = 1;
                army = 1;
                dfs(j, i);
                if(ground[i][j] == 'B') blue += pow(army, 2);
                else white += pow(army, 2);
            }
        }
    }
    cout << white << " " << blue << endl;
    return 0;
}

 

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

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

//
//  main.cpp
//  BJ1303
//
//  Created by Hwayeon on 2021/08/30.
//

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int N, M;
int blue, white = 0;
char ground[100][100] = {'W', };
int visit[100][100] = {0, };

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[y][x] = 1;
    int cnt = 0;
    
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        cnt ++;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = now_x+dx[i];
            int ny = now_y+dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(visit[ny][nx] == 1) continue;
            if(ground[ny][nx] != ground[now_y][now_x]) continue;
            q.push({nx, ny});
            visit[ny][nx] = 1;
        }
    }
    if(ground[y][x] == 'B') blue += pow(cnt, 2);
    else white += pow(cnt, 2);
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            scanf("%1s", &ground[i][j]);
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(visit[i][j] == 0){
                bfs(j, i);
            }
        }
    }
    cout << white << " " << blue << endl;
    return 0;
}

---

풀이 과정

풀이 과정 24분

1. DFS

#include <iostream>
#include <math.h>
using namespace std;

int N, M;
int blue, white = 0;
char ground[100][100] = {'W', };
int visit[100][100] = {0, };

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int army = 0;

void dfs(int x, int y){
	//인접한 4 방향 탐색
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        //범위를 벗어난 경우 무시한다
        if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
        
        //이미 방문한 노드인 경우 무시한다
        if(visit[ny][nx]) continue;
        
        //적군이라면 무시한다
        if(ground[ny][nx] != ground[y][x]) continue;
        
        //아군인 경우, 방문처리하고 카운팅, dfs 탐색을 이어간다
        visit[ny][nx] = 1;
        dfs(nx, ny);
        army++;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//문자 하나씩 입력 받기
            scanf("%1s", &ground[i][j]);
        }
    }
    
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//방문하지 않은 노드가 있는 경우, DFS를 호출하여 뭉친 병사수를 구한다
            if(visit[i][j] == 0){
            	//시작 노드 방문처리, 병사수 1로 초기화
                visit[i][j] = 1;
                army = 1;
                dfs(j, i);
                
                //위력 카운팅
                if(ground[i][j] == 'B') blue += pow(army, 2);
                else white += pow(army, 2);
            }
        }
    }
    cout << white << " " << blue << endl;
    return 0;
}
//시간복잡도 = O(n^2), 공간복잡도 = O(n^2)

 

2. BFS

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int N, M;
int blue, white = 0;
char ground[100][100] = {'W', };
int visit[100][100] = {0, };

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int x, int y){
    queue<pair<int, int>> q;
    
    //시작 노드 위치 q에 삽입, 방문 처리, 병사수 0으로 초기화
    q.push({x, y});
    visit[y][x] = 1;
    int cnt = 0;
    
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        //병사수 카운팅
        cnt ++;
        q.pop();
        
        //인접한 4 방향 탐색
        for(int i=0; i<4; i++){
            int nx = now_x+dx[i];
            int ny = now_y+dy[i];
            //범위를 벗어난 경우 무시한다
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            
            //이미 방문한 노드인 경우 무시한다
            if(visit[ny][nx] == 1) continue;
            
            //적군인 경우 무시한다
            if(ground[ny][nx] != ground[now_y][now_x]) continue;
            
            //아군인 경우, 방문처리 하고 다음 탐색을 위해 큐에 삽입한다
            q.push({nx, ny});
            visit[ny][nx] = 1;
        }
    }
    //위력을 카운팅 한다
    if(ground[y][x] == 'B') blue += pow(cnt, 2);
    else white += pow(cnt, 2);
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//문자 하나씩 입력 받기
            scanf("%1s", &ground[i][j]);
        }
    }
    
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
        	//방문하지 않은 노드인 경우, 해당 노드를 시작노드로 하여 BFS 탐색 시작
            if(visit[i][j] == 0){
                bfs(j, i);
            }
        }
    }
    cout << white << " " << blue << endl;
    return 0;
}
//시간복잡도 = O(n^2), 공간복잡도 = O(n^2)