백준 JAVA 3184 양 리뷰

문제풀이

양 중심으로 dfs 돌렸고 양 만날때, 늑대 만날때 나눠서 수를 셌다.

그리고 양이나 늑대가 울타리로 감싸져서 고립되어있을때 양은 for문으로 전체적으로 순회할때 고립된 것까지 셀 수 있지만

늑대는 고립되어있으면 dfs로 확인할 방법이 없기 때문에 dfs가 모두 끝난후 마지막에 for문을 다시 돌면서 방문하지 않은 늑대 수를 세었다.

dfs가 끝날때마다 양 수와 늑대 수를 비교해서 양이 이기는지 늑대가 이기는지 판단을 했고 총 양 수, 늑대 수를 갱신했다.

전형적인 dfs bfs 문제이고 쉬운 문제였다. dfs/bfs 유형은 아직까진 전형화되어있고 쉬운 문제만 풀 수 있다.

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

public class Main{
    static char[][] gragh;
    static boolean[][] visited;
    static int r,c;
    static int[] dirX={0,0,-1,1};
    static int[] dirY={-1,1,0,0};
    static int sheep,wolf;
    static int anssheep,answolf;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

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

        for(int i=0;i<r;i++){
            String str =br.readLine();
            for(int j=0;j<c;j++){
                gragh[i][j]=str.charAt(j);
            }
        }
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(gragh[i][j]=='o'&&!visited[i][j]){
                    visited[i][j]=true;
                    wolf=0;
                    sheep=1;
                    dfs(i,j);
                    if(sheep>wolf){
                        wolf=0;
                    }else{
                        sheep=0;
                    }
                    anssheep+=sheep;
                    answolf+=wolf;
                }
            }
        }
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++) {
                if(visited[i][j]==false){
                    if(gragh[i][j]=='v'){
                        visited[i][j]=true;
                        answolf++;
                    }
                }
            }
            }
        System.out.println(anssheep+" "+answolf);

    }
    static void dfs(int x, int y){
        for(int i=0;i<4;i++){
            int nowx=x+dirX[i];
            int nowy=y+dirY[i];

            if(nowx>=0&&nowy>=0&&nowx<r&&nowy<c){
                if(gragh[nowx][nowy]!='#'&&!visited[nowx][nowy]){
                    if(gragh[nowx][nowy]=='o'){
                        sheep++;
                    }
                    if(gragh[nowx][nowy]=='v'){
                        wolf++;
                    }
                    visited[nowx][nowy]=true;
                    dfs(nowx,nowy);
                }
            }
        }

    }
}