[백준] 1303 - 전쟁 - 전투

1. 문제

1303번 - 전쟁 - 전투

2. 개요

가로 N, 세로 M 크기의 전쟁터에 병사들이 있다.

아군은 W 적군은 B로 표시한다.

병사들이 가로, 세로로 인접해있다면 이들을 뭉쳐있다고 하며 N명이 뭉쳐있다면 N^2의 전력을 낼 수 있다.

이 때 아군의 전력과 적군의 전력을 각각 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

모든 칸을 탐색하며 방문하지 않았다면 DFS로 탐색을 시작한다.

DFS에서는 현재 칸의 상하좌우 칸이 전쟁터 내 유효범위인지, 이미 방문했는지, 현재 위치의 값과 똑같은지를 판단한다.

처음 dfs를 시작했을 때의 칸의 값이 W라면 최종 cnt를 제곱한 값만큼 아군의 전력에 더하고 B였다면 적군의 전력에 더해준 후, 최종으로 두 값을 출력한다.

3-2. Python

import sys

def DFS(y, x, cnt):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= M or nextX < 0 or nextX >= N:
            continue
        
        if visited[nextY][nextX] == 1:
            continue

        if board[nextY][nextX] != board[y][x]:
            continue

        visited[nextY][nextX] = 1
        cnt = DFS(nextY, nextX, cnt + 1)

    return cnt

N, M = map(int, sys.stdin.readline().split())

myvalue, enemyvalue = 0, 0

board = []
visited = [[0 for i in range(N)] for j in range(M)]

for i in range(M):
    board.append(list(sys.stdin.readline().rstrip()))

for i in range(M):
    for j in range(N):
        if visited[i][j] == 0:
            visited[i][j] = 1

            if board[i][j] == 'W':
                myvalue += DFS(i, j, 1) ** 2

            else:
                enemyvalue += DFS(i, j, 1) ** 2

print(myvalue, enemyvalue)

3-3. C#

namespace boj_1303
{
    internal class Program
    {
        static char[,] board;
        static bool[,] visited;
        static int N;
        static int M;
        static int[] dirY = { -1, 0, 1, 0 };
        static int[] dirX = { 0, -1, 0, 1 };

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            N = int.Parse(input[0]);
            M = int.Parse(input[1]);

            board = new char[M, N];
            visited = new bool[M, N];

            for (int i = 0; i < M; i++)
            {
                string rows = Console.ReadLine();
                for (int j = 0; j < N; j++)
                {
                    board[i, j] = rows[j];
                }
            }

            int myvalue = 0;
            int enemyvalue = 0;

            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (!visited[i, j])
                    {
                        visited[i, j] = true;

                        if (board[i, j] == 'W')
                            myvalue += (int)MathF.Pow(DFS(i, j, 1), 2);

                        else
                            enemyvalue += (int)MathF.Pow(DFS(i, j, 1), 2);
                    }
                }
            }

            Console.WriteLine($"{myvalue} {enemyvalue}");
        }

        static int DFS(int y, int x, int count)
        {
            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= M || nextX < 0 || nextX >= N)
                    continue;

                if (visited[nextY, nextX])
                    continue;

                if (board[nextY, nextX] != board[y, x])
                    continue;

                visited[nextY, nextX] = true;
                count = DFS(nextY, nextX, count + 1);
            }

            return count;
        }
    }
}