백준 1303 전쟁 - 전투 python, java

DFS, BFS를 이용하여 간단하게 풀 수 있는 문제였다.
단, 보통 다른 문제에서는 N을 세로, M을 가로로 준다.
하지만 이문제는 N을 가로, M을 세로로 준다. 문제를 꼼꼼히 읽자!

📜 문제 바로 가기 : 전쟁 - 전투

제출코드

파이썬

import sys
input = sys.stdin.readline

delta = [(0,1), (0,-1), (1,0), (-1,0)]
M, N = map(int, input().split())
arr = [input().rstrip() for _ in range(N)]
visited = [[False] * M for _ in range(N)]
white, blue = 0, 0

def getPower(i, j):
    color = arr[i][j]
    visited[i][j] = True
    value = 0
    stack = [(i, j)]
    while stack:
        i, j = stack.pop()
        value += 1
        for di, dj in delta:
            ni, nj = i+di, j+dj
            if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == color and visited[ni][nj] == False:
                visited[ni][nj] = True
                stack.append((ni, nj))
    
    return value ** 2
        

for i in range(N):
    for j in range(M):
        if visited[i][j] == False:
            value = getPower(i, j)
            if arr[i][j] == "W":
                white += value
            else:
                blue += value

print(white, blue)

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static Main solve = new Main();
    static boolean[][] visited;
    static String[][] arr;
    static Delta[] delta = new Delta[4];
    static int N;
    static int M;

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

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        visited = new boolean[N][M];


        delta[0] = new Delta(-1, 0);
        delta[1] = new Delta(1, 0);
        delta[2] = new Delta(0, -1);
        delta[3] = new Delta(0, 1);

        arr = new String[N][M];
        for (int i = 0; i < N; i++) {
            String info = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = String.valueOf(info.charAt(j));
            }
        }

        double white = 0;
        double blue = 0;
        for (int i=0; i < N; i++) {
            for (int j=0; j < M; j++) {
                if (visited[i][j] == false) {
                    if (arr[i][j].equals("W")) {
                        white += solve.getPower(i, j);
                    } else {
                        blue += solve.getPower(i, j);
                    }
                }
            }
        }

        System.out.println((int) white + " " + (int) blue);
    }

    public double getPower(int i, int j) {
        int value = 0;
        String color = arr[i][j];
        visited[i][j] = true;
        Node st = new Node(i, j);
        ArrayList<Node> stack = new ArrayList();
        stack.add(st);

        while (stack.isEmpty() == false) {
            Node node = stack.remove(stack.size()-1);
            value += 1;

            for (Delta d : delta) {
                Node newNode = new Node(node.i + d.i, node.j + d.j);
                if ((isRange(newNode)) && (color.equals(arr[newNode.i][newNode.j])) && (visited[newNode.i][newNode.j] == false)) {
                    visited[newNode.i][newNode.j] = true;
                    stack.add(newNode);
                }
            }
        }
        return Math.pow(value, 2);
    }

    public boolean isRange(Node node) {
        int i = node.i;
        int j = node.j;
        if ((0 <= i) && (i < N) && (0 <= j) && (j < M)) {
            return true;
        }
        return false;
    }
}

class Node {
    int i;
    int j;

    public Node(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

class Delta {
    int i;
    int j;

    public Delta(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

---

접근방법

배열을 완전탐색하면서 방문을 하지 않은 좌표라면 DFS(or BFS)를 실행한다.