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

문제

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

1303번: 전쟁 - 전투

설명

입출력

나의 풀이

풀이 과정

문제의 예제로 설명을 하자면 옷 색으로 전쟁터가 표현되어 있다. 

아군 (흰색) - W

적군 (파란색) - B 

구해야 할 것은 아군의 위력의 합과 적군의 위력의 합을 출력하는 것이다. 

뭉쳐있는 병사들의 위력은 제곱이 된다고 문제에 나와 있는데 아래의 그림처럼 위력이 계산된다. 

상하좌우로 인접한 경우가 뭉쳐있는 것이므로 제곱이 적용된 위력을 계산하면 아래와 같다.

아군(W) = 9^2 + 7^2 = 130

적군(B) = 1^2 + 8^2 = 65 

 

위의 풀이 아이디어를 바탕으로 구현하였다. 

문제 풀이 코드

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

public class Main {

    static int[] dr = {-1,1,0,0}; // 행
    static int[] dc = {0,0,-1,1}; // 열

    static int re_w = 0;
    static int re_b = 0;

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

        int n = Integer.parseInt(st.nextToken()); // 가로 크기
        int m = Integer.parseInt(st.nextToken()); // 세로 크기

        String[][] war = new String[m][n];

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

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

        int w = 0; // 우리팀
        int b = 0;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (!visited[r][c] && war[r][c].equals("W")) {
                    dfs("W",r,c,war,visited);
                    w = w + (int) Math.pow(re_w, 2);
                    re_w = 0;
                } else if (!visited[r][c] && war[r][c].equals("B")) {
                    dfs("B",r,c,war,visited);
                    b = b + (int) Math.pow(re_b, 2);
                    re_b = 0;
                }
            }
        }

        System.out.println(w + " " + b);
    }

    public static void dfs(String start,int r,int c , String[][] war, boolean[][] visited) {
        visited[r][c] = true;
        if (start.equals("W")) re_w++;
        else re_b++;

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr >= 0 && nr < war.length && nc >= 0 && nc < war[0].length && !visited[nr][nc] && war[nr][nc].equals(start)) {
                dfs(start, nr, nc, war, visited);
            }
        }
    }
}

문제를 풀기 위해 사용된 알고리즘은 dfs이다. (bfs도 가능하다.)

우선 2차원 배열 war과 visited에 입력으로 들어온 전쟁터와 방문 체크용 배열을 생성하였다. 

그리고 war의 각각의 칸마다 방문을 안 했으면 dfs를 시도하도록 for문을 돌려주었다. 

각 칸마다 dfs를 돌았을 경우 W 덩어리 또는 B 덩어리를 탐색하기 때문에

dfs를 돌며 한 덩어리가 몇 칸인지 re_w, re_b에 담아줄 수 있다. 

이렇게 한 번의 dfs를 끝낼 때마다 덩어리의 칸 수를 제곱해서 w와 b 변수에 넣어 주면

w와 b 에는 각각 아군, 적군의 위력의 합이 담기게 된다. 

마지막으로 w 와 b를 출력해 주었다. 

 

**

한번에 통과하진 못했는데 

이유는 행과 열(가로, 세로)를 헷갈렸고 

dfs에서 상하좌우 좌표를 탐색활 때 war 배열을 벗어나는 것을 막아주는 if 조건을 빼먹었다.

사소한 실수 금.지!

그래도 내 힘으로 dfs 도 구현하고 그럴듯하게 잘 풀었다~~