DFS

백준 1303번을 DFS 를 이용해 Java 로 풀어봤다. DFS 문제 중 level 1에 해당하는 문제라는데... 험난했다...

일단 BufferedReader 를 통해 String 을 Char 배열로 받는 것조차 제대로 기억나지 않아 이것부터 다시 찾아봤다... 좌절감을 느꼈지만 다시 Java 에 익숙해지기 위한 시간을 견뎌야 하는 것으로 받아들였다.
BufferedWriter 를 통해 int 값을 출력하려는데 계속 출력되지 않아 이것도 찾아보니 BufferedWriter 로 출력할 때는 String 으로 바꿔준 후에 출력이 가능하다는 것도 다시금 배웠다. 역시 쓰지 않으면 잊어먹을 수밖에 없다는 것을 다시 느꼈다...

BufferedWriter 의 write 메소드

왜 int 형이 출력되지 않는지 알아보기 위해 cmd+B 를 이용해서 살펴봤더니... 왜 그런지 알 수 있었다.

문제로 돌아와서, W끼리 뭉쳐있는 그룹과 B끼리 뭉쳐있는 그룹을 나누어 각 그룹의 수를 counting 해줘야 하는데 여기서 또다시 막혔다. map[0][0]을 출발점으로 해서 첫 W 그룹은 어찌저찌 counting 하더라도... 그 외의 남아있는 3개 그룹은 어떻게 counting 해줘야 하는지 고민이 됐다.

visited 를 통해 검사해주기!

for 문을 이용해 visited 이중 배열을 돌며 아직 방문하지 않은 지점들에 대해 dfs를 돌면 된다!
이 방식을 통해 방문하지 않은 지점을 만날 때마다 W 그룹과 B 그룹에 각각 counting 해준 값들을 추가해주면 된다.

DFS 구현 방식은 이전에 풀은 1260번과 동일하게 재귀( Recursion ) 을 이용해 구현했다.

아래는 제출한 코드다.

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

public class boj1303 {
    static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bfw;
    static StringTokenizer stk;
    static int N; // 가로
    static int M; // 세로
    static String input;
    static char[][] map;
    static boolean[][] visited;
    static int[] directionRow = { -1, 1, 0, 0}; // 상하좌우 순서
    static int[] directionCol = { 0, 0, -1, 1};
    static int ally = 0;
    static int enemy = 0;
    static int count = 0;

    static void dfs(int row, int col, char whoIsIt){
        visited[row][col] = true;
        count += 1;

        for(int i=0; i<4; i++){
            int newRow = row + directionRow[i];
            int newCol = col + directionCol[i];
            if(0<=newRow && newRow<M && 0<=newCol && newCol<N && map[newRow][newCol] == whoIsIt && !visited[newRow][newCol]){
                dfs(newRow, newCol, map[newRow][newCol]);
            }
        }
    }

    public static void main(String args[]) throws IOException {
        stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        map = new char[M][N];
        visited = new boolean[M][N];

        for(int i=0; i<M; i++){
            String s = bfr.readLine();
            map[i] = s.toCharArray();
        }

        for(int row=0; row<M; row++){
            for(int col=0; col<N; col++){
                if(!visited[row][col]){ // 아직 방문하지 않은 녀석들을 차례로 순회해주자
                    count = 0;
                    dfs(row, col, map[row][col]);

                    if(map[row][col]=='W') // 아군이면 ally에 추가해주고
                        ally += count*count;
                    else // 적구이면 enemy 에 추가해주자
                        enemy += count*count;
                }
            }
        }
        bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        bfw.write(String.valueOf(ally) + " " + String.valueOf(enemy));
        bfw.close();
    }
}

오늘 배운 것

1. String 하나를 Char 배열로 받을 때는
   string.toCharArray() 메소드를 사용하면 된다.
2. BufferedWriter 는 String 형태로 출력한다.