백준 1303번(Java) : 전투

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

1303번: 전쟁 - 전투

 

---

[풀이]

 

 DFS를 이용하여 문제를 풀었다. 그래프를 돌면서 'W'일 때와 'B'일때를 구분해서 개수를 더해주는 식으로 풀이를 진행했다. 그래프 문제와 DFS를 구현할 줄 알면 크게 어렵지는 않았던 것 같다.

 

 최근에 있었던 시험도 그렇고 항상 느끼는게 DFS와 BFS 그리고 그래프에 대해서 부족한게 많다고 느껴서 한동안은 이 부분에 집중할 생각이다. 그래서 개념도 다시 한번 공부하고, 전에 보던 알고리즘 책도 다시 보면서 문제를 풀었다. 처음에는 문제에서 주어진 N과 M이 헷갈려서 IndexOutOfBounds에 대해서 많이 오류가 생겼다. 그리고 전에 기본적인 DFS와 BFS문제를 풀다가 이런 문제를 푸니 뭔가 또 갈피를 못잡는 느낌이 들었다. 

 

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static boolean[][] visited;
    static String[][] arr;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int white_count = 0;
    static int black_count = 0;

    static class Node {
        int x;
        int y;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader((System.in)));
        String s = bufferedReader.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new String[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            String line = bufferedReader.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = line.substring(j, j + 1);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == false) {
                    if (arr[i][j].equals("B")) {
                        int num = bfs("B", i, j);
                        black_count += Math.pow(num, 2);
                    } else if (arr[i][j].equals("W")) {
                        int num = bfs("W", i, j);
                        white_count += Math.pow(num, 2);
                    }
                }
            }
        }
        System.out.println(white_count + " " + black_count);
    }

    public static int bfs(String color, int y, int x) {
        int count = 1;
        Queue<Node> queue = new LinkedList<>();
        visited[y][x] = true;
        queue.offer(new Node(y, x));

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_x = now.x + dx[i];
                int now_y = now.y + dy[i];

                if (now_x >= 0 && now_x < n && now_y >= 0 && now_y < m) {
                    if (visited[now_y][now_x] == false && color.equals(arr[now_y][now_x])) {
                        queue.offer(new Node(now_y, now_x));
                        visited[now_y][now_x] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }
}