백준 3184번 : 양 (Java)

🔗 문제 링크

 

3184번: 양

---

📖 풀이 과정

- DFS 를 이용한 그래프 유형의 문제입니다. (재귀를 이용한 DFS로 풀었습니다.)

- 다른 그래프 문제와의 차이를 보자면, 늑대와 양의 수를 매번 확인하여 계산된 값을 구해야 합니다.

- 이를 위해, dfs() 메소드를 호출하기 위해서는 '.', 'v', 'o' 이어야 하며 방문하지 않은 곳이어야 합니다.

- dfs() 메소드가 끝날 때마다 늑대의 수가 양의 수 이상일 경우에는 양은 0이 되고 그 반대의 경우에는 늑대가 0이 됩니다.
  - 이렇게 남은 값을 각각의 전체 변수에 더해줍니다.
  
- 기존의 문제와 달리 추가해야할 조건과, 계산 부분에 대해서 조금만 더 신경쓰면 충분히 풀 수 있다고 생각합니다.

---

💻 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static char[][] arr;
    static boolean[][] visited;
    static int r,c,totalW,totalS, wolf, sheep;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,-1,0,1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sb = new StringBuffer();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        totalS = 0;
        totalW = 0;

        arr = new char[r][c];
        visited = new boolean[r][c];

        for(int i = 0; i < r; i++){
            String input = br.readLine();
            for(int j = 0; j< c; j++){
                arr[i][j] = input.charAt(j);
            }
        }

        for(int i = 0; i< r; i++){
            for(int j = 0; j< c; j++){
                wolf = 0;
                sheep = 0;
                if(!visited[i][j]) {
                    if(arr[i][j] == 'v' || arr[i][j] == '.' || arr[i][j] == 'o') {
                        solve(i, j);
                    }
                }
                if(sheep > wolf){
                    wolf = 0;
                }else{
                    sheep = 0;
                }
                totalW += wolf;
                totalS += sheep;
            }
        }
        sb.append(totalS).append(" ").append(totalW);
        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();
    }

    private static void solve(int x, int y){
        visited[x][y] = true;

        if(arr[x][y] == 'o'){
            sheep += 1;
        }else if(arr[x][y] == 'v'){
            wolf += 1;
        }

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

            if(nextX >= 0 && nextY >= 0 && nextX < r && nextY < c){
                if(!visited[nextX][nextY]){
                    if(arr[nextX][nextY] == '.' || arr[nextX][nextY] == 'v' || arr[nextX][nextY] == 'o'){
                        solve(nextX, nextY);
                    }
                }
            }
        }
    }
}