1303번 - 4방향 탐색(dfs)

문제:

위의 입력과 같이 주어진다.

가로, 세로가 N, M으로 주어진다.

다음 M개 줄에 B와 W가 적혀져 있으며, N개가 뭉쳐있을 때는 N^2의 위력을 낼 수 있다.

W와 B의 위력을 알아내라.

 

풀이:

어떤 문자가 모여있는 것은 해당 문자 주변을 탐색해서 찾아내야 할 것이다.

고로 아래와 같은 과정으로 생각해보았다.

 

• 현재 위치에서 4방향(상, 하, 좌, 우)으로 이동하면서 같은 문자(B 또는 W)를 찾는다.
• 이동할 수 있는 방향으로 이동해 다시 4방향(상, 하, 좌, 우)를 둘러본다.
• 다시 돌아가지 않기 위해 들렸던 위치에는 흔적을 남긴다.
• 더이상 이동 할 수 없다면, (해당 구역의 합)^2을 저장한다.

이렇게 생각해보니까 dfs()를 사용하고 있다는 것을 눈치챘다.

가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상 갈 수 없을 때 돌아와 다른 경로를 탐색하는 방식이 완전 dfs()이다!

 

 

위 방식으로 작성한 코드는 아래와 같다.

import java.io.*;

public class 전쟁전투_1303번 {
    static int N, M;
    static char[][] map;
    static boolean[][] visited;
    static int[] xMove = {1, -1, 0, 0};
    static int[] yMove = {0, 0, 1, -1};
    static int sum = 0;
    static int bSum = 0;
    static int wSum = 0;

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

        String[] dimensions = br.readLine().split(" ");
        N = Integer.parseInt(dimensions[0]);
        M = Integer.parseInt(dimensions[1]);

        map = new char[M][N];
        for (int i = 0; i < M; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        visited = new boolean[M][N];
        for (int y = 0; y < M; y++) {
            for (int x = 0; x < N; x++) {
                if (!visited[y][x]) {
                    if (map[y][x] == 'B') {
                        solider(y, x, 'B');
                        bSum += sum * sum;
                        sum = 0;
                    } else {
                        solider(y, x, 'W');
                        wSum += sum * sum;
                        sum = 0;
                    }
                }
            }
        }

        System.out.println(wSum + " " + bSum);

    }

    static void solider(int y, int x, char word) {
        visited[y][x] = true;
        sum++;
        for (int i = 0; i < 4; i++) {
            if (y+yMove[i] >= 0 && y+yMove[i] < M && x+xMove[i] >= 0 &&x+xMove[i] < N) {
                if(!visited[y+yMove[i]][x+xMove[i]] && map[y+yMove[i]][x+xMove[i]] == word) {
                    solider(y+yMove[i], x+xMove[i], word);
                }
            }
        }
    }
}

 

1. 모든 노드를 탐색하기 시작한다.
2. 만일 해당 노드에 들린 적이 없다면 solider()메서드를 호출한다.
   1. solider()메서드는 y, x, word를 입력값으로 받고, word는 B인지 W인지가 적혀져있다.
   2. 입력된 y, x 위치를 들렸다고 체크한다.
   3. 한 명이 더 온것이기에 sum에 1을 더한다.
   4. yMove와 xMove 배열에 미리 이동할 방향(동서남북)이 저장되어 있다.
   5. 해당 배열들을 이용해 y, x를 동서남북으로 한칸씩 이동해주며, soilder메서드를 호출해준다.
   6. 해당위치에 모여있는 모든 병사들을 탐색하면, 재귀가 종료되며, 몇명의 병사가 있는지 sum에 저장되어 있다,.
3. B의 합 또는 W의 합에 sum^2을 더해주며, sum을 0으로 초기화한다.
4. 위과정이 끝난 후 W의 합과 B의 합을 출력한다.

 

이번에는 단 한번도 막히지 않았고, 얼마전에 비슷한 문제를 풀면서 고생한 보람을 느꼈다.