양치기 꿍 - 3187

문제

풀이

import java.util.*;

public class ex3187 {

    static int n,m;
    static char[][] board;
    static boolean[][] ch;
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static int wolf=0,sheep=0;
    static int all_wolf=0,all_sheep=0;

    public static void DFS(int x,int y){
        ch[x][y] = true;
        if(board[x][y]=='k') sheep++;
        else if(board[x][y]=='v') wolf++;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && !ch[nx][ny] && board[nx][ny]!='#'){
                DFS(nx,ny);
            }
        }
    }
    public static void solution(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]!='#' && !ch[i][j]){
                    wolf=0;
                    sheep=0;
                    DFS(i,j);
                    if (wolf >= sheep) all_sheep -= sheep;
                    else all_wolf -= wolf;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        board = new char[n][m];
        ch = new boolean[n][m];

        for(int i=0; i<n; i++){
            char[] str = sc.next().toCharArray();
            for(int j=0; j<m; j++){
                board[i][j] = str[j];
                if(board[i][j]=='k') all_sheep++;
                else if(board[i][j]=='v') all_wolf++;
            }
        }
        solution();
        System.out.println(all_sheep + " " + all_wolf);
    }
}

우선 , 내 기준에서는 어려운 DFS였다. 그리고 처음에 많이 헤맸는데, 이번 문제 풀이를 통해서 더더욱 DFS를 단단한 기본기를 가지자.

1. 우선 주어지는 n,m만큼 board를 만들어준다. 그에 맞는 ch체크배열도 생성해준다. board를 생성할때 양과 늑대일경우 총 양과 총 늑대의 양을 미리 체크해둔다.
2. solution()함수에서 탐색시작!! 체크배열이 false이면서 '#'이 아닌 경우 DFS(i,j)를 호출한다. 나는 이 경우를 어떠한 한 곳의 울타리 안이라고 하겠다. DFS()를 호출하면서 울타리 안으로 들어가는 것이다.
3. DFS()함수 시작!! DFS에 들어오면 해당 위치의 체크배열을 true로 만들어준다. 재방문 금지를 위해서. 그런 후 해당 x,y좌표의 값이 양인지 늑대인지 체크해준다.
4. 양과 늑대는 상하좌우 4가지 방향으로 이동가능하기때문에 다음 좌표 nx,ny에서의 양,늑대를 찾기 위해서 4가지 방향의 nx,ny를 조건에 맞게 다시 DFS()를 호출시키면서 그 해당 울타리 안의 늑대와 양의 마리 수를 체킹한다.
5. 해당 울타리에서의 체킹이 끝나고, solution()으로 돌아왔을때 늑대가 양보다 같거나 많을 경우에는 양의 마리 수를 줄이고, 양이 많으면 늑대의 마리 수를 줄인다. 이런 식으로 총 남게 되는 양과 늑대의 마리 수를 출력한다.