백준 1303 : 전투 DFS BFS 풀이

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

1303번: 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

입력

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

출력

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

 

문제 풀이 방법

이 문제는 사실 다른 DFS, BFS 문제와 크게 다르지 않다. 다만 몇 가지 주의해야할 점이 있다.

1. 입력받는 n 이 가로이고, m 이 세로이다 => 

- 이중 for 문의 경우 바깥쪽 for문은 세로의 크기이고, 안쪽 for 문은 가로의 크기 이기 때문에 for 문  기존과는 다르게 반대로 사용하는 것에 주의해야한다.

- 세로의 크기라는 것은 결국 y 이고, 가로의 크기란 결국 x 이기 때문에 battle[i][j] 를 받아가는 경우 battle[x][y] 가 아닌 battle[y][x] 임에 주의한다 => 이 부분 때문에 문제는 일찍 풀었는데...내가 풀고, 맞아놓고도 이해하는데 엄청 오래걸렸다

2. 입력을 숫자로 받는 것이 아닌 2개의 문자 - B, W - 로 받는다. 이 때문에 문자를 숫자로 바꿔서 저장하거나 문자 그대로 저장한 후 check 배열을 따로 생성하는 등의 추가 조건이 필요하다.

=> 나는 B W 를 각각 1과 2로 변경하여 저장하고, 방문할때도 따로 배열을 만들지 않고 하나의 배열에서 끝낼 수 있도록 코드를 짰다.

3. 병사들은 가로 세로로 연결되며 연결되었을 때 전투력은 연결된 병사들의 수^2 이다.

4. DFS 가 BFS 보다 빠르다! 아마 BFS 는 클래스를 하나 더 사용하기 때문이 아닐까...생각한다.

아래가 DFS 위가 BFS, DFS 가 더 빠르다

 

DFS

아래의 BFS 와 차이점은 Queue 를 사용하지 않고 재귀 함수를 사용하며, cnt 변수를 사용한다.

이때 cnt 변수는 static 으로 선언되어서 재귀함수가 한 번 돌때마다 +1 된다.

자세한 건 코드 주석!

package baekJoon;

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

public class Quiz_1303_DFS {
    static int[] dx = {0, 0, -1, 1}; // x 좌표로 움직이기 배열
    static int[] dy = {-1, 1, 0, 0}; // y 좌표로 움직이기 배열

    static int[][] battle; // 싸움영역 배열

    static int n, m; // 각각 가로, 세로 ==> y, x
    static int b, w; // b 는 적군, w 는 아군의 총 전투력
    static int cnt; // 최대로 연결된 병사들의 수를 확인하기 위한 cnt

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 열 = col = 가로의 크기 = x
        m = Integer.parseInt(st.nextToken()); // 행 = row = 세로의 크기 = y


        battle = new int[m][n]; // 이중 for문은 [row][col] => y,x

        // 이중 for 문 시작
        // 입력받은 글자가 W 라면 1, B 라면 2로 배열에 저장
        for(int i=0; i<m; i++){ // 바깥 for 문은 세로의 크기 = row = y
            char[] arr = br.readLine().toCharArray();
//            System.out.println(Arrays.toString(arr));
            for (int j = 0; j < n; j++) { // 안쪽 for문은 가로의 크기 = col = x
                if (Objects.equals(arr[j], 'W')) { // 만약 입력받은 글자가 W 라면 1
                    battle[i][j] = 1;
                }else if(Objects.equals(arr[j], 'B')){ // 만약 입력받은 글자가 B 라면 2
                    battle[i][j] = 2;
                }
//                System.out.print(battle[i][j]+" ");
            }
//            System.out.println();
        }

        // 역시 이중 for 문 시작
        // 만약 battle[i][j] 의 값이 1이나 2라면 해당 좌표를 방문한다.
        // 이때 현재 어떤 값을 기준으로 방문했는지 확인하기 위해서 findPower 에 1이나 2를 들고 방문하게 된다.
        // 방문 후에는 해당 좌표를 0 으로 변경해준다.
        // 이후 메서드가 종료되면 cnt 값을 제곱후 w 나 b 에 더한다.
        for(int i=0; i<m; i++){
            int result = 0; // 결과 변수 안쪽 for 문이 한번 끝날때마다 초기화
            for(int j=0; j<n; j++){
                cnt = 1;

                if (battle[i][j] == 1) { // 1을 확인후
                    battle[i][j] = 0;  // 방문하고 0 으로 변경
                    findPower(i, j, 1); // 현재 i, j 값을 갖고 방문
                    result = (int) Math.pow(cnt, 2);
                    w+=result;
                } else if(battle[i][j] == 2){
//                    System.out.println(i + " " + j);
                    battle[i][j] = 0;
                    findPower(i, j, 2);
                    result = (int)Math.pow(cnt, 2);
                    b+=result;
                }
            }
        }
        bw.append(w+" "+b);
        bw.flush();
        bw.close();


    }

    // DFS 시작
    // DFS 에서 중요한 것은 받아오는 i, j 가 단순히 x, y 순서가 아닌 y, x 순서라는 점에 주의한다.
    // 때문에 battle[ny][nx] 를 기준으로 비교를 해야한다.
    // nx, ny 는 0 보다 커야하며 각각 nx 는 n 보다 작아야하고, ny 는 m 보다 작아야한다.
    // 또한 내가 다음 방문하는 곳인 battle[ny][nx] 는 num 이여야한다.
    // 왜냐하면 앞서서 num 인 곳은 기준으로 방문했기 때문에 같은 색 - 같은 num - 인 경우에만 방문 할 수 있다
    static void findPower(int y, int x, int num){

        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m && battle[ny][nx] == num) {
                battle[ny][nx] = 0;
                cnt++;
                findPower(ny, nx, num);


            }
        }
    }
}

 

BFS

이 문제를 처음 봤을 때 사실 BFS 로 먼저 풀이를 도전했었다. 아마 이전에 풀었던 섬찾기 문제랑 뭔가 비슷하다고 느껴서 그런 것 같다. 사실 요즘에 이런 문제들은 죄다 BFS 로 만 푸는 듯하다ㅋㅋ

기본 주의점은 위에 적어놓은 것과 같고, DFS 와 가장 다른 점이라면 역시 Queue 를 사용한다는 것 정도? 나머지는 사실 DFS 코드와 크게 다를게 없을 듯하다.

- BFS 는 DFS 와 다른점만 주석으로 적어두었습니다.

package baekJoon;

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

public class Quiz_1303_BFS {
    static int[] dx = {-1, 1, 0, 0}; // 움직임 배열 x
    static int[] dy = {0, 0, -1, 1}; // 움직이기 배열 y

    static int[][] battle; // 전투 배열

    static int n, m; // 가로, 세로
    static int b, w; // 각각 적군, 아군

    static Queue<FindFriend> q = new LinkedList<FindFriend>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 가로 = col = x
        m = Integer.parseInt(st.nextToken()); // 세로 = row = y

        battle = new int[m][n]; // new int[row][col]

        for(int i=0; i<m; i++){ // 바깥쪽 for 문은 row = 세로의 크기
            char[] arr = br.readLine().toCharArray();
//            System.out.println(Arrays.toString(arr));
            for (int j = 0; j < arr.length; j++) { // 안쪽 for 문은 col = 가로의 크기
                if (Objects.equals(arr[j], 'W')) {
                    battle[i][j] = 1;
                }else if(Objects.equals(arr[j], 'B')){
                    battle[i][j] = 2;
                }
//                System.out.print(battle[i][j]+" ");
            }
//            System.out.println();
        }


        for(int i=0; i<m; i++){ // 바깥 for 문은 row = y = 세로의 크기
            int result = 0; //
            for(int j=0; j<n; j++){ // 안쪽 for 문은 col = x = 가로의 크기
                if (battle[i][j] == 1) {
                    q.add(new FindFriend(i,j));
                    battle[i][j] = 0;
                    result = (int)Math.pow(findPower(1, 1), 2);
                    w+=result;
                }else if(battle[i][j] == 2){
//                    System.out.println(i + " " + j);
                    q.add(new FindFriend(i,j));
                    battle[i][j] = 0;
                    result = (int)Math.pow(findPower(1, 2), 2);
                    b+=result;
                }
            }
        }
        bw.append(w+" "+b);
        bw.flush();
        bw.close();


    }

    // q가 비어있지 않은 동안 계속 반복됨
    // 움직임 배열 dx, dy 를 이용해 nx, ny 생성
    // nx, ny 는 0보다 크며, 각각 n, m 보다 작아야한다.
    // 또한 battle[ny][nx] 로 받아야한다는 것에 유의한다.
    static int findPower(int cnt, int num){
        while (!q.isEmpty()) {
            FindFriend now = q.poll();

            for(int i=0; i<4; i++){
                int nx = now.x+dx[i];
                int ny = now.y+dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < m && battle[ny][nx] == num) {
                    battle[ny][nx] = 0;
                    cnt++;
                    q.add(new FindFriend(ny, nx));

                }
            }
        }

        return cnt;
    }
}

class FindFriend{
    int x, y;

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