[백준] 1303번. 전쟁 - 전투(JAVA)

문제

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

---

풀이(32분)

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

public class Main {

    static int n, m, count;
    static char[][] arr;
    static boolean[][] visited;
    static Queue<Point> q = new LinkedList<>();
    static int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new char[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            String input = br.readLine();
            for(int j = 0; j < n; j++){
                arr[i][j] = input.charAt(j);
            }
        }

        int answerW = 0;
        int answerB = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    count = 1;
                    visited[i][j] = true;
                    q.add(new Point(i, j));
                    bfs();
                    if (arr[i][j] == 'W') {
                        answerW += count * count;
                    } else {
                        answerB += count * count;
                    }
                }
            }
        }

        System.out.println(answerW + " " + answerB);
    }

    static void bfs() {
        while (!q.isEmpty()) {
            Point point = q.poll();
            int nowX = point.x;
            int nowY = point.y;

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + direction[i][0];
                int nextY = nowY + direction[i][1];

                // 배열 범위 내에 있는지 확인
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
                    // 방문하지 않았고, 현재 좌표와 같은 색인 경우에만
                    if (!visited[nextX][nextY] && arr[nowX][nowY] == arr[nextX][nextY]) {
                        count++;
                        visited[nextX][nextY] = true;
                        q.add(new Point(nextX, nextY));
                    }
                }
            }
        }
    }

    static class Point {
        int x, y;

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

 

코드와 문제를 보면 알 수 있듯이 간단한 bfs문제이다.

하지만 시간은 32분이나 걸렸다... 왜일까..?

 

코드를 보면 알 수 있지만 일반적으로 쓰는 [n][m] 이 아닌 [m][n]을 배열로 선언해줘야 한다.

예제에는 5 5로 제시되기 때문에 문제를 꼼꼼히 읽고 조건을 파악하지 않으면 놓칠 수 있는 문제이다.

 

문제 조건을 꼼꼼히 읽고 가로와 세로를 정확하게 구분하자!!!