백준 3184번 양(JAVA) - DFS

백준 3184번

 

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

3184번: 양

 

 

문제설명

마당의 정보가 주어진다.

'.'(점) : 빈필드

# : 울타리

'o' : 양

'v' : 늑대

필드에서는 수평/수직으로만 이동가능하며 울타리를 지나지 않고 이동할 수 있다면 같은 영역이라고 본다.

한 영역안에서 양의 수가 많으면 늑대와 싸워 이길수 있고 쫓아낸다. 그렇지 않다면 양이 잡아먹힌다.

살아남은 양과 늑대의 수를 출력

 

 

접근

DFS로 접근

 

코드

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

public class Main {
    static int []dx = {-1,0,1,0};
    static int []dy = {0,1,0,-1};
    static char [][]map;
    static boolean [][]visit;
    static int R;
    static int C;
    static int []ans = new int[2];
    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());
        // .: 땅, #: 울타리, V: 늑대, O: 양
        map = new char[R][C];
        visit = new boolean[R][C];

        int s = 0;
        int w = 0;

        for(int i=0;i<R;i++){
            String temp = br.readLine();
            for(int j=0;j<C;j++){
                map[i][j] = temp.charAt(j);
            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(!visit[i][j] && !(map[i][j] == '#')){
                    ans[0]=ans[1]=0;
                    int []x = dfs(i,j);
                    if( !(x[0] == 0 && x[1] == 0)){
                        if(x[1] >= x[0]){
                            w += x[1];
                        }else if(x[1] < x[0]){
                            s += x[0];
                        }
                    }

                }
            }
        }
        System.out.println(s);
        System.out.println(w);
    }
    static int[] dfs(int x,int y){

        visit[x][y] = true;
        if(map[x][y] == 'o')
            ans[0]++;
        if(map[x][y] == 'v')
            ans[1]++;

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

            if(nx < 0 || ny < 0 || nx >= R || ny >=C) continue;
            if(visit[nx][ny] || map[nx][ny]=='#') continue;
            dfs(nx,ny);
        }

        return ans;
    }
}

 

풀이

1. 수평,수직으로 움직일 dx,dy선언

2. 마당의 정보를 받을 map, 방문여부를 담을 visit 선언

3. 배열 ans를 선언하는데 이것은 dfs를 돌고 양의 수와 늑대의 수를 리턴 받을 변수이다.(dfs내부에서 영역별로 몇마리 있는지 알아내기 위함)

4. 행과열 크기 받고 마당의 정보를 입력받는다.

5. s,w는 최종 양과 늑대의 수

6. 2차원배열 크기만큼 반복문을돌며 방문하지 않았으며, 울타리가 아닌경우 해당 좌표를 dfs돈다.(돌기전에  ans 0으로 초기화)

7. dfs에서 o이면 ans[0]증가, v이면 ans[1]증가 / 울타리가 아니고 방문하지 않았으면  dfs 호출하도록 구현

8. 저장된 ans를 리턴하고 영역별로 늑대의 수가 양의 수보다 같거나 많다면 늑대의 수만 w에 더해줌. 그렇지 않고 양의 수가 더 많다면 양의 수만 s에 추가