[BOJ 3184] 양 (Java, 그래프 탐색)

 

---

문제 링크 

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

3184번: 양

---

풀이

- 전형적인 격자형 그래프 문제

- 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

- '.' (점)은 빈 필드를, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미

- 상하좌우로만 이동가능하며, 울타리는 이동 불가

- (조건) 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다

- 영역별로 늑대의 수와 양의 수를 비교하여 살아 남은 양과 늑대의 수를 출력

- 시간 복잡도 : O(N^2) , 최대 N = 250인 경우에 Integer로 처리가능

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int R, C, SHEEP, WOLF;

    static int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static boolean[][] visit;

    static String[] MAP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visit = new boolean[R][C];
        MAP = new String[R];
        for(int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            MAP[i] = st.nextToken();
        }
    }

    static void bfs(int i, int j) {
        Queue<Integer> que = new LinkedList<>();
        que.add(i);
        que.add(j);
        visit[i][j] = true;

        int _wolf = 0, _sheep = 0;
        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll();

            if(MAP[x].charAt(y) == 'v') _wolf += 1;
            if(MAP[x].charAt(y) == 'o') _sheep += 1;

            for(int k = 0; k < 4; k++) {
                int nx = x + direction[k][0];
                int ny = y + direction[k][1];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if(visit[nx][ny]) continue;
                if(MAP[nx].charAt(ny) == '#') continue;

                que.add(nx);
                que.add(ny);
                visit[nx][ny] = true;
            }
        }

        if(_sheep == 0 && _wolf == 0) return;

        if(_sheep > _wolf) SHEEP += _sheep;
        else WOLF += _wolf;
    }

    static void pro() {
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(!visit[i][j] && MAP[i].charAt(j) != '#') {
                    bfs(i, j);
                }
            }
        }

        sb.append(SHEEP).append(" ").append(WOLF);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

 

DFS로 풀 경우

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int R, C, SHEEP, WOLF, _S, _W;

    static int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static boolean[][] visit;

    static String[] MAP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visit = new boolean[R][C];
        MAP = new String[R];
        for(int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            MAP[i] = st.nextToken();
        }
    }

    static void dfs(int x, int y) {
        visit[x][y] = true;
        if(MAP[x].charAt(y) == 'v') _W += 1;
        if(MAP[x].charAt(y) == 'o') _S += 1;

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

            if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if(visit[nx][ny]) continue;
            if(MAP[nx].charAt(ny) == '#') continue;

            dfs(nx, ny);
        }
    }

    static void pro() {
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(!visit[i][j] && MAP[i].charAt(j) != '#') {
                    _W = 0;
                    _S = 0;
                    dfs(i, j);

                    if(_S > _W) SHEEP += _S;
                    else WOLF += _W;
                }
            }
        }

        sb.append(SHEEP).append(" ").append(WOLF);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}