[백준(BOJ)] 1303번: 전쟁 - 전투 (DFS/BFS, C++)

📝 문제풀이 과정

---

이번 문제도 BOJ:2667(단지번호붙이기) 문제와 유사하다.

각 병사 graph[x][y]를 기준으로 상, 하, 좌, 우의 4가지 경우에만 인접한 것으로 간주한다.

x-1 y

x y-1

x y+1

x+1 y

따라서 graph[x][y] 기준 위의 4가지 경우에 대해 해당 정점이 방문하지 않았고, graph[x][y]와 값이 같으면 방문한다. 그리고 인접한 것으로 cnt를 증가시킨다.

이때 다음 방문하는 graph[nx][ny]에서 nx와 ny는 전쟁터 M x N 크기 범위 내에 있는 것을 대상으로 탐색한다.

만약 초기 graph[x][y]에 대한 함수 호출이 끝나고 main 함수로 리턴하면 graph[x][y] 기준 모든 인접한 정점들에 대해 방문한 것으로, cnt에 대한 값의 제곱을 W이었으면 result[0]에, B이었으면 result[1]에 더해간다.

 

 

💻 C++ 제출코드

---

#include <iostream>
#include <deque>
using namespace std;
int visited[100][100];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

void DFS(int x, int y, deque<char> *graph, int *cnt, int N, int M){
    (*cnt)++;
    visited[x][y] = 1;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i]; int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
        if(!visited[nx][ny] && graph[nx][ny] == graph[x][y]) DFS(nx, ny, graph, cnt, N, M);
    }
}

int main(){
    int N, M; // N: 가로, M: 세로
    scanf("%d %d", &N, &M);
    deque<char> graph[M];
    deque<int> result;
    result.push_back(0);
    result.push_back(0);

    for(int i=0; i<M; i++){
        string str;
        cin >> str;
        for(char c: str) graph[i].push_back(c);
    }
    
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            int cnt=0;
            if(!visited[i][j]){
                DFS(i, j, graph, &cnt, N, M);
                if(graph[i][j] == 'W') result[0] += cnt*cnt;
                else result[1] += cnt*cnt;
            }
        }
    }
    printf("%d %d\n", result[0], result[1]);
}

❗❗ 주의해야 할 점은, 가로가 M이고, 세로가 N이다. 즉, x에 대한 범위가 0~M-1까지, y에 대한 범위가 0~N-1까지이다.

계속 오답을 받는다면, 이 부분을 다시 확인해보자. 

 

 

👏 결과

---