자바(Java) 알고리즘 문제풀이 전쟁 - 전투 [백준 / DFS]

출처 - 구글 이미지

 

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

1303번: 전쟁 - 전투

 

 

풀이 코드

DFS 완전 탐색으로 풀이했다. 주의할 점은 가로의 크기가 N, 세로의 크기가 M 이라고 명시되어있는 점을 주의하자.

나는 원래 세로 길이를 N, 가로 길이를 M 으로 했었기 때문에 입력 순서를 뒤바꿔줘서 [N][M] 으로 이차원 배열을 만들 수 있게 했다.

그리고 띄워쓰기 없이 board 가 입력되기 때문에 split() 을 활용해서 board 를 셋팅해줬다.

 

DFS 메서드 호출을 이중 반복문 내부에서 호출해본적이 처음이라 시간이 굉장히 오래 걸린 문제 .. ㅎㅎ

방문하지 않았을 때, 팀 컬러가 같은 경우를 분기문으로 잘 처리해줘야 한다 !!

count 세는 부분 또한 DFS 호출 시 최소 W 또는 B 병사가 한 명은 있기 때문에 바로 count 를 1 증가시켜줘야지 엄한데서 count 증가 시켜버리면 이상한 답이 나오니 주의하자. 이렇게 바로 count 증가시킬거 아니면 다음 경로에 방문 표시한 부분 아래에서 count 를 증가시키고 String teamColor = map[i][j]; 아래 count 는 0 이 아니라 1로 초기화 시켜줘야 한다.

package backjoonsliver.dfs;

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

public class 전쟁_전투_Review {
    static int N;
    static int M;
    static int wCount;
    static int bCount;
    static int count = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static String[][] map;
    static boolean[][] visited;

    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());
        map = new String[N][M];
        visited = new boolean[N][M];

        // 1. 초기 격자판 생성
        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = line[j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                if (!visited[i][j]) {
                    String teamColor = map[i][j];
                    count = 0; // 아군인 경우에서 적군인 경우로 넘어가서 세줄 때 count 를 초기화 시켜줘야함
                    DFS(i, j, teamColor);

                    // 아군인 경우
                    if (teamColor.equals("W")) {
                        wCount += count * count;

                        // 적군인 경우
                    } else {
                        bCount += count * count;
                    }
                }
            }
        }
        System.out.println(wCount);
        System.out.println(bCount);
    }

    private static void DFS(int x, int y, String color) {
        visited[x][y] = true; // 방문 check
        count++; // 맨 처음 W 또는 B 일 때 병사 수가 최소 1이므로
        
        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 && !visited[nx][ny] && map[nx][ny].equals(color)) {
                visited[nx][ny] = true; // 다음 경로에 방문 표시 check
                DFS(nx, ny, color);
            }
        }
    }
}