[BOJ] 1303: 전쟁 - 전투 (JAVA)

문제

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

 

여담

처음에 가로 크기와 세로 크기를 제대로 안 읽어서 틀렸다..ㅎㅎ 가로 크기가 N, 세로 크기가 M이다! 잘 읽고 문제를 풀자.

 

풀이

W로 이루어진 영역에 존재하는 우리 병사의 수, B로 이루어진 영역에 존재하는 적국 병사의 수를 구한 뒤 white와 blue 변수에 제곱 값을 더하면 된다.

 

즉, BFS나 DFS를 사용해서 각 영역에 존재하는 같은 팀 병사의 수를 구해서 풀면 된다.

 

코드

BFS

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;
    static int white = 0, blue = 0;
    static char[][] map;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[M][N];
        visited = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, map[i][j]);
                }
            }
        }
        System.out.println(white + " " + blue);
    }

    public static void bfs(int x, int y, char color) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        int total = 0;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            total++;

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= M || ny >= N || visited[nx][ny]) {
                    continue;
                }

                if (map[nx][ny] == color) {
                    queue.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        total = (int) Math.pow(total, 2);
        if (color == 'W') white += total;
        else blue += total;
    }
}

 

DFS

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;
    static int white = 0, blue = 0, area;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static char[][] map;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[M][N];
        visited = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    area = 0;
                    dfs(i, j, map[i][j]);
                    area = (int) Math.pow(area, 2);
                    if (map[i][j] == 'W') white += area;
                    else blue += area;
                }
            }
        }
        System.out.println(white + " " + blue);
    }

    public static void dfs(int x, int y, char color) {
        area++;
        visited[x][y] = true;

        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 || visited[nx][ny]) {
                continue;
            }

            if (map[nx][ny] == color) {
                dfs(nx, ny, color);
            }
        }
    }
}

---