[백준] (JAVA) 3184 : 양

문제

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

3184번: 양

설명

입출력

나의 풀이

풀이 과정

문제는 전체 마당에서 울타리를 기준으로 각 영역에서 양과 늑대의 수를 파악하는 것이 핵심이다. 

예제 1번을 보기 쉽게 그림으로 표현하면 아래와 같다.

울타리를 제외한 칸을 탐색하며 늑대 수와 양의 수를 파악하기 위해서는 dfs 또는 bfs를 이용할 수 있다. 

우선 문제를 풀기 위한 계획을 세웠다.

1. 입력값으로 들어온 마당을 2차원 배열 madang과 방문 확인을 위한 2차원 배열 visited를 생성한다.

2. madang의 각 칸을 확인하며 울타리가 아니고 방문을 안 했으면 dfs를 돌린다. 

3. dfs안에서는 방문 처리와 늑대, 양의 수를 갱신해 주고 같은 영역 안에 있는 칸을 탐색하며 재귀적으로 dfs를 반복한다.

4. main 함수에서 각 dfs가 끝나면 같은 영역의 모든 칸을 탐색했으므로 늑대와 양의 수를 비교하여 

    승리한 동물의 수를 갱신해 준다.

 

위의 계획을 바탕으로 코드를 구현하였다.

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

public class success {

    static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}}; // {행,열} 기준 상하좌우

    static int v;
    static int o;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        String[][] madang = new String[R][C];

        // 마당 입력 받기
        for (int i = 0; i < R; i++) {
            String string = br.readLine();
            for (int j = 0; j < C; j++) {
                madang[i][j] = String.valueOf(string.charAt(j));
            }
        }
        // 방문 배열 생성
        boolean[][] visited = new boolean[R][C];

        int sum_v = 0;
        int sum_o = 0;

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                v = 0;
                o = 0;
                if (!madang[r][c].equals("#") && !visited[r][c]) {
                    dfs(r, c, madang, visited);
                    if (v >= o) sum_v += v;
                    else sum_o += o;
                }
            }
        }
        System.out.println(sum_o+" "+sum_v);
    }

    static public void dfs(int r, int c, String[][] madang, boolean[][] visited) {
        visited[r][c] = true;
        if (madang[r][c].equals("o")) o++;
        else if (madang[r][c].equals("v")) v++;

        for (int i = 0; i < 4; i++) {
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];
            if (nr < 0 || nr > madang.length - 1 || nc < 0 || nc > madang[0].length - 1) continue;

            if (!madang[nr][nc].equals("#") && !visited[nr][nc]) {
                dfs(nr, nc, madang, visited);
            }
        }
    }
}

 

이제 좌표평면에서 사방을 이동하며 dfs로 영역을 탐색하는 류의 문제 유형에 익숙해진 것 같다.

원래 입력 문법이나 dfs 구현 등을 기본 문법에서 참고하며 풀었었는데 

이번에는 다른 자료 하나도 안 보고 빠른 시간 안에 구현했다!!! 

완전 뿌--듯🐥