[JAVA] 백준 양

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

 

dfs 탐색을 통해서 네방향으로 나아간다.

grid에 양과 늑대를 반영하지 않고 count값만 저장하여 최종결과를 도출할 때에 활용했다.

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

public class Main {
​​​​static int R, C;
​​​​static int wolf = 0, sheep = 0;
​​​​static int resultWolf = 0, resultSheep = 0;
​​​​static boolean visited[][];
​​​​static char[][] grid;

​​​​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());
​​​​​​​​visited = new boolean[R][C];
​​​​​​​​grid = new char[R][C];
​​​​​​​​for (int i = 0; i < R; i++) {
​​​​​​​​​​​​String line = br.readLine();
​​​​​​​​​​​​for (int j = 0; j < line.length(); j++) {
​​​​​​​​​​​​​​​​grid[i][j] = line.charAt(j);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​for (int i = 0; i < R; i++) {
​​​​​​​​​​​​for (int j = 0; j < C; j++) {
​​​​​​​​​​​​​​​​wolf = 0;
​​​​​​​​​​​​​​​​sheep = 0;//양/늑대 초기화
​​​​​​​​​​​​​​​​if (!visited[i][j]) dfs(i, j);
​​​​​​​​​​​​​​​​if (sheep > wolf) wolf = 0;
​​​​​​​​​​​​​​​​else sheep = 0;

​​​​​​​​​​​​​​​​resultSheep += sheep;
​​​​​​​​​​​​​​​​resultWolf += wolf;
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​System.out.println(resultSheep + " " + resultWolf);
​​​​}

​​​​static int[] dr = {0, 1, 0, -1};//우상좌하
​​​​static int[] dc = {1, 0, -1, 0};

​​​​static void dfs(int r, int c) {//영역순회
​​​​​​​​visited[r][c] = true;

​​​​​​​​if (grid[r][c] == 'o') ++sheep;
​​​​​​​​if (grid[r][c] == 'v') ++wolf;

​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​int newR = r + dr[d];
​​​​​​​​​​​​int newC = c + dc[d];
​​​​​​​​​​​​if (boundaryCheck(newR, newC) && !visited[newR][newC] && grid[newR][newC] != '#') {
​​​​​​​​​​​​​​​​dfs(newR, newC);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​static boolean boundaryCheck(int r, int c) {
​​​​​​​​return (r < R && c < C && r >= 0 && c >= 0);
​​​​}
}