[코테] 백준 3187 양치기 꿍: DFS Java

해당 문제는 DFS보다 BFS로 더 많이 푸는 것 같다.

난 DFS로 풀었다.

 

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

 

1) 입력 부분

    static int inWolf = 0;
    static int inSheep = 0;
    // 빈 공간 = .
    // 울타리 = #
    // 늑대 = v 양 = k
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken()); // 세로 길이
        int C = Integer.parseInt(st.nextToken()); // 가로 길이


        String[][] space = new String[R][C];
        visited = new boolean[R][C];

        int wolfCount = 0;
        int sheepCount = 0;

        for (int i = 0; i < R; i++) space[i] = br.readLine().split(""); // 마당의 각 행을 입력받아 저장


        System.out.print(sheepCount + " " + wolfCount);

        br.close();
    }

처음 입력을 받을 때 양과 늑대의 갯수를 저장하여서,

이후 dfs 문에서 울타리 안의 양이나 늑대를 빼주는 방법도 있다.

그러나 br.readLine().split("");으로 한번에 입력을 받는 게 간결하고 좋아보여서 처음 입력 받을 때 양과 늑대의 갯수를 저장하지 않는 방법을 사용했다.

 

2) DFS 로직

처음에는 '울타리'에 집착해서 어려웠다.

울타리 안에 있는 늑대와 양의 갯수를 구해야하니까... 울타리인 곳이라면 dfs 함수를 타야 하나라고 생각했다.

 

그런데 집중해야할 포인트는 '울타리로 막히지 않은 영역에는 양과 늑대가 없으며'이다.

즉, 울타리가 나올때까지의 양과 늑대의 갯수를 세면 된다. 

 

    public static void dfs(int x, int y, String[][] space) {
        visited[y][x] = true;

        if(space[y][x].equals("v")) {
            inWolf++;
        } else if (space[y][x].equals("k")) {
            inSheep++;
        }

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

            if (nx >= 0 && ny >= 0 && ny < space.length && nx < space[y].length) {
                if (!visited[ny][nx] && !space[ny][nx].equals("#")) {
                    dfs(nx, ny, space);
                }
            }
        }
    }

 

 

전체 코드

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

public class baekjoon_3187 {

    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0};
    static int[] dy = { 0, 0, -1, 1};

    static int inWolf = 0;
    static int inSheep = 0;
    
    // 빈 공간 = .
    // 울타리 = #
    // 늑대 = v 양 = k
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken()); // 세로 길이
        int C = Integer.parseInt(st.nextToken()); // 가로 길이


        String[][] space = new String[R][C];
        visited = new boolean[R][C];

        int wolfCount = 0;
        int sheepCount = 0;

        for (int i = 0; i < R; i++) space[i] = br.readLine().split(""); // 마당의 각 행을 입력받아 저장

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {

                if(!visited[i][j] && !space[i][j].equals("#")) {
                    dfs(j, i, space);

                    if(inSheep>inWolf) {
                        sheepCount += inSheep;
                    } else {
                        wolfCount += inWolf;
                    }

                    inWolf = 0;
                    inSheep = 0;
                }

            }

        }


        System.out.print(sheepCount + " " + wolfCount);

        br.close();
    }

    public static void dfs(int x, int y, String[][] space) {
        visited[y][x] = true;

        if(space[y][x].equals("v")) {
            inWolf++;
        } else if (space[y][x].equals("k")) {
            inSheep++;
        }

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

            if (nx >= 0 && ny >= 0 && ny < space.length && nx < space[y].length) {
                if (!visited[ny][nx] && !space[ny][nx].equals("#")) {
                    dfs(nx, ny, space);
                }
            }
        }
    }
}

 

DFS에 대한 감이 조금 잡혔다.

다음 한 문제 풀어보고 BFS로 넘어가야겠다.