[BOJ ]전쟁 - 전투(1303)

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

풀이날짜 : 2021/04/06

난이도 : 실버1(solved.ac참조)

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int N, M;
    static int[][] mtx;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1, 0, 0};
    static int dfs(int color, int y, int x){
        int sum =1;
        mtx[y][x]=0;    // 재 탐색 방지
        for(int i =0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(mtx[ny][nx]==color){
                sum+=dfs(color, ny, nx);
            }
        }
        return sum;
    }
    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());
        mtx=new int[M+2][N+2];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken().toString();
            for(int s = 0; s<str.length(); s++){
                if(str.charAt(s)=='W') mtx[i][s+1]= 1;
                else mtx[i][s+1]= -1;
            }
        }

        int W=0, B=0;
        for(int i =1; i<=M; i++){
            for(int j =1; j<=N; j++){
                int color  = mtx[i][j];
                if(color==0) continue;
                int x = dfs(color, i, j);
                x*=x;
                if(color==1)    // 아군
                    W+=x;
                else                // 적군
                    B+=x;   
            }
        }
        System.out.println(W+" "+B);
    }

}

풀이

단순한 DFS로 문제를 풀었다. BFS도 가능하지만 개인적으로 DFS로 구현하는 게 더 편하다.

1. 우선 mtx에 W와 B를 받는다. (나의 경우에는 int형으로 변환하여 문제를 푸는 것을 더 선호하기 때문에 W를 1 B를 -1로 바꿔줬다.

※mtx의 크기는 주어진 크기보다 2 크게(new int[M+2][N+2])하여 시작과 끝을 여유 공간으로 해놓는다. 이렇게 하면 if(0<=i && i<N) 과 같은 처리를 하지 않고 mtx[i][j]의 값만 비교해 주면된다. 기본으로 0이 들어가 있으니 mtx가 color와 다르면 처리하지 않으면 된다.

 

2. mtx[1][1]부터 mtx[M][N]까지 이중 for문을 통해 순회하며 dfs 함수를 호출하여 인접노드를 방문한다.

※이때 중복탐색이 되지 않도록 mtx[y][x]는 W와 B의 값(1, -1)이 아닌 0으로 바꿔준다.

 

 

3. 한번의 dfs가 끝나면 x에 값을 저장해 x*x를 해주고 color가 W(1)였으면 W변수에 B(-1)이었으면 B변수에 더해준다.

※이중 for문 부분의 color를 미리 저장해 두지 않고 mtx[i][j]를 통해 참조를 하면 dfs를

 

4. 순회를 마쳤으면 출력하며 마무리한다.