Q. 3184 자바 : 양

Q. 3184 자바 : 양

 

문제 : boj.kr/3184

실버 1 난이도의 문제이다.

 

격자형 그래프에 양, 늑대, 울타리가 주어지고, 

울타리 내에 양과 늑대의 수를 비교해서, 양이 더 많을경우 늑대를 없애고

늑대와 양의 수가 같거나 늑대가 많을 경우 양을 없앤다.

이후 모든 울타리에 생존한 양과 늑대에 수를 출력하는 문제이다.

 

생각해야 되는 입력값이 빈 필드, 양, 늑대, 울타리이고,

이걸 어떻게 탐색을 하면 될까 고민해서 아래와 같은 방식으로 풀었다.

1. 처음 시작할 때는 양이나 늑대일 경우 탐색을 시작한다.

(모든 탐색 여부는 visit[][] 배열에 표시)

2. 이후 다른 영역을 탐색할 때는 울타리가 아닌 경우 무조건 탐색을 한다.

3. 위 탐색이 한 번 끝나면 양과 늑대의 수를 비교해 조건에 따라 출력할 결과값에 더해준다.

 

이 코드의 시간복잡도는

1. 모든 정점에 대한 DFS or BFS 순회 - O(RC)

따라서 약 O(RC) 정도의 시간복잡도를 가진다고 예상할 수 있다.

 

격자형 그래프 탐색의 경우 시간 복잡도가 전체 크기에 비례하므로 이를 확인해보니

가로 세로인 R, C의 최대값이 250인것을 확인했고 따라서 시간초과는 걱정하지 않아도 된다.

 

그래프를 입력받는데 사용한 자료형은 입력되는 자료가

양, 늑대, 빈 필드, 울타리로 타입이 세개라 char를 이용한 2차원 배열을 사용했다.

 

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

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

    static int R, C, cntO = 0, cntV = 0, curO = 0, curV = 0;
    static char[][] graph;
    static boolean[][] visit;

    static int[] dy = new int[]{0, 1, 0, -1};
    static int[] dx = new int[]{1, 0, -1, 0};

    static void input() {

        R = scan.nextInt();
        C = scan.nextInt();
        graph = new char[R][C];
        visit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            graph[i] = scan.nextLine().toCharArray();
        }
    }

    static void dfs(int y, int x) {

        visit[y][x] = true;
        char c = graph[y][x];
        if (c == 'o') curO++;
        if (c == 'v') curV++;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny == -1 || nx == -1 || ny == R || nx == C) continue;
            if (visit[ny][nx]) continue;
            if (graph[ny][nx] == '#') continue;
            dfs(ny, nx);
        }
    }

    static void bfs(int y, int x) {

        Queue<int[]> que = new LinkedList<>();
        visit[y][x] = true;
        que.add(new int[] {y, x});

        while (!que.isEmpty()) {

            int[] point = que.poll();
            char c = graph[point[0]][point[1]];
            if (c == 'o') curO++;
            if (c == 'v') curV++;

            for (int i = 0; i < 4; i++) {
                int ny = point[0] + dy[i];
                int nx = point[1] + dx[i];
                if (ny == -1 || nx == -1 || ny == R || nx == C) continue;
                if (visit[ny][nx]) continue;
                if (graph[ny][nx] == '#') continue;
                que.add(new int[] {ny, nx});
                visit[ny][nx] = true;
            }
        }
    }

    static void pro() {

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if ((graph[i][j] == 'o' || graph[i][j] == 'v') && !visit[i][j]) {
                    curO = 0;
                    curV = 0;
                    bfs(i, j);
                    // dfs(i, j);
                    if (curO > curV) cntO += curO;
                    else cntV += curV;
                }
            }
        }
        sb.append(cntO).append(' ').append(cntV);
        System.out.println(sb);
    }

    public static void main(String[] args) {

        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}