[백준] 3187 : 양치기 꿍 (JAVA)

난이도

🥈 1

 

링크

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

3187번: 양치기 꿍

---

문제

---

풀이과정

해당 문제는 그래프의 전형적인 문제이다.

BFS()를 사용해서 풀었고, 그래프의 문제들은 풀이 방법이 고정적이고 조금씩 바뀌기 때문에 

백준을 시작할 때 가장 풀기 좋은 유형이 아닐까 싶다!

 

해당 문제도 그래프 문제의 전형적인 패턴을 따르면 되는 문제였다.

 

1) 입력받은 값들을 배열에 저장

2) 방문하지 않은 곳이면서 울타리가 아닌 부분에서 BFS() 진행

3) BFS() 탐색을 하며 늑대 or 양이라면 각각의 수 증가

4) 탐색이 끝난 후 양의 수가 늑대보다 많을 경우 양의 수를 증가 / 아니라면 늑대의 수 증가

5) 모든 배열 탐색 후 결과값 출력

 

🚨 탐색해야 하는 부분이 울타리가 아닌 부분들이다!

       (양이나 늑대가 울타리 안에 있는지 판단해야 된다고 생각했는데 그냥 울타리 안을 탐색하면서 울타리라면 pass / 방문한 곳이라면 pass 이렇게 풀면 된다!)

---

전체 코드

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

public class Main {

    private static int R, C;
    private static int v, k;

    private static int[] dR = {-1, 1, 0, 0};
    private static int[] dC = {0, 0, -1, 1};

    private static char[][] map;
    private static boolean[][] isVisit;

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

        st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        isVisit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String input = br.readLine();

            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        search();

        sb.append(k).append(" ").append(v);

        System.out.println(sb);
    }

    private static void search() {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (isVisit[i][j]) {
                    continue;
                }
                if (map[i][j] != '#') {
                    bfs(i, j);
                }
            }
        }
    }

    private static void bfs(int row, int col) {
        Queue<Node> q = new LinkedList<>();

        q.offer(new Node(row, col));
        isVisit[row][col] = true;

        int wolf = 0;
        int sheep = 0;

        while (!q.isEmpty()) {
            Node vertex = q.poll();

            if (map[vertex.row][vertex.col] == 'v') {
                wolf++;
            }
            else if (map[vertex.row][vertex.col] == 'k') {
                sheep++;
            }

            for (int i = 0; i < 4; i++) {
                int dr = vertex.row + dR[i];
                int dc = vertex.col + dC[i];

                if (dr < 0 || dr >= R || dc < 0 || dc >= C) {
                    continue;
                }
                if (isVisit[dr][dc]) {
                    continue;
                }
                if (map[dr][dc] == '#') {
                    continue;
                }

                q.offer(new Node(dr, dc));
                isVisit[dr][dc] = true;
            }
        }

        if (sheep > wolf) {
            k += sheep;
        }
        else {
            v += wolf;
        }
    }
}

class Node {
    int row, col;

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

 

결과