[Silver I/JAVA] 3187 양치기 꿍

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

 

 

조건

• 양 > 늑대 -> 양만 남음 , 늑대 >= 양 -> 늑대만 남음
• 울타리 바깥에는 양 늑대 없음
• 빈공간 있음

 

필요한 것

• 방문 여부 체크
• 방향 이동 배열 dx, dy
• 울타리, 빈공간, 양늑대 입력 받을 map 배열
• 입력을 공백없이 받음 (charAt 사용)

 

풀이 과정

• 방문한 적 없고, 울타리가 아니면 BFS 탐색
• 상하좌우 방향 이동하면서 BFS 탐색을 하고 늑대와 양의 개수를 각각 카운트
• 마지막에 최종 늑대와 양의 개수를 비교
• 좌표 형태로 큐에 한번에 담을 수 있음

 

전체 코드

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

public class Main{
    static int R,C; //가로C,세로R
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int wolf = 0;
    static int sheep = 0;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        R = Integer.parseInt(str[0]); //세로
        C = Integer.parseInt(str[1]); //가로
        
        map = new char[R][C];
        visited = new boolean[R][C];
        
        //map초기화
        for(int i=0; i<R; i++){
            String s = br.readLine();
            for(int j=0; j<C; j++){
                map[i][j] = s.charAt(j);
            }
        }
        
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                //방문x 울타리x
                if(!visited[i][j] && map[i][j] != '#'){
                    bfs(i,j);
                }
            }
        }
        
        //결과 출력
        System.out.println(sheep + " " + wolf);
    }
    
    private static void bfs(int x, int y){
        //좌표형태로 저장하기 위한 큐 선언
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y}); //크기가 2인 정수배열 값 추가
        visited[x][y] = true;
        
        int sheepCnt = 0;
        int wolfCnt = 0;
        
        if(map[x][y] == 'k') sheepCnt++;
        if(map[x][y] == 'v') wolfCnt++;
        
        while(!queue.isEmpty()){ //큐에 값이 있으면 반복
            int[] current = queue.poll(); //현재값 꺼냄
            int currentX = current[0];
            int currentY = current[1];
            
            for(int i=0; i<4; i++){
                int nx = currentX + dx[i];
                int ny = currentY + dy[i];
                
                if(nx >= 0 && nx < R && ny >= 0 && ny < C && !visited[nx][ny] && map[nx][ny] != '#'){
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                    
                    //양, 늑대 카운트
                    if(map[nx][ny] == 'k') sheepCnt++;
                    if(map[nx][ny] == 'v') wolfCnt++;
                }
            }
        }
        
        if(sheepCnt > wolfCnt){ //양>늑대 -> 양 개수만 남음
            sheep += sheepCnt;
        }else{
            wolf += wolfCnt;
        }
    }
}