양 - 3184

문제

풀이

package Baekjoon;

import java.util.Scanner;

// 양 - DFS
public class ex3184 {
    static int n,m;
    static char[][] map;
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static int answerO = 0 , answerV=0;
    static int nowO=0;
    static int nowV=0;

    public static void DFS(int x,int y){
        if(map[x][y]=='o') nowO++;
        else if(map[x][y]=='v') nowV++;

        map[x][y]='#';
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny]!='#'){
                DFS(nx,ny);
            }
        }
    }
    public static void solution(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j]=='.' || map[i][j]=='v' || map[i][j]=='o'){
                    DFS(i,j);
                    if(nowO > nowV){
                        answerO += nowO;
                    }
                    else answerV += nowV;
                }
                nowO=0;
                nowV=0;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        map = new char[n][m];
        for(int i=0; i<n; i++){
            char[] str = sc.next().toCharArray();
            for(int j=0; j<m; j++){
                map[i][j] = str[j];
            }
        }

        solution();
        System.out.println(answerO + " " + answerV);
    }
}

오랜만에 DFS 기본이 되는 문제! 원샷원킬!
DFS의 핵심. 기본 DFS 템플릿 구조를 이해해야하며, DFS() 호출 전에 탐색하는 solution() 함수를 잘 작성해야한다.

이 문제의 경우 한 곳의 울타리를 찾아서 그곳에서의 살아남는 양과 늑대의 현황을 종합해서 출력하는 문제이다.

처음에 '.' 나왔을 때만 DFS()를 호출했는데, 자세히 보니까 그냥 울타리 안에 늑대나 양만 있는 경우도 있을 수 있더라. 그래서 고쳐주고 정답 돌렸는데 바로 클리어!