[백준] 3184번 양

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q3184.java

울타리 안에 양과 늑대가 있다. 양이 더 많을 경우 늑대가 죽고 그 외는 늑대가 양을 잡아먹는다.
울타리는 #로 구별되어 있으며 하나라도 이어져있으면 같은 울타리 안이다.
하루 밤이 지났을 때 살아남은 양과 늑대의 수를 출력하여라.

처음 생각

맵을 탐색해서 결과를 도출하는 전형적인 BFS 탐색 문제인것 같다. 이동할 수 없는 지역(#)이 아닌 곳에서 부터 탐색을 시작해 방문체크를 해가면서 상 하 좌 우로 이동이 가능하면 queue에 넣어준다.

다음 생각

양과 늑대의 수를 세야하므로 v나 o가 들어오면 각 변수를 +1 시켜준다. 양과 늑대의 수를 센후 해당 울타리에서 이동 할 수 있는 경로가 없어 빠져나오게되면 조건대로 늑대의 수가 많을 경우 전체 늑대수에 더해주고, 반대의 경우는 전체 양수에 해당 양수를 더해준다.

▶ 양과 늑대의 개수가 계속 그대로나와서 보니 queue에 add를 안해주고 있었다. 하하하하.

다다음 생각

BFS 탐색을 해보기 좋은 문제였다.

▶ 아직 익숙치 않다면 미로 탐색(https://www.acmicpc.net/problem/2178) 문제를 먼저 풀어보는게 좋을 것 같다.

방안

1) 꼼꼼히 풀자.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

package baekjoon.q1000;   import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;   public class Q3184 {     static int r,c;     static int[][] arr;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         r = sc.nextInt();         c = sc.nextInt();         arr = new int[r][c];         for(int i=0;i<r;i++) {             String t = sc.next();             for(int j=0;j<c;j++)                 arr[i][j] = t.charAt(j);         }         // 방문 표시         visited = new boolean[r][c];         for(int i=0;i<r;i++) {             for(int j=0;j<c;j++) {                 // 돌아다닐 수 있는 공간이 있으면 돌아다니자.                 if(arr[i][j]!='#'&&!visited[i][j])                     solve(i,j);             }         }         System.out.println(tSheep+" "+tWolf);     }          static int tWolf,tSheep;     static boolean[][] visited;     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static void solve(int x,int y) {         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(x,y));         visited[x][y] = true;         int wolf = 0,sheep = 0;         // 시작 위치가 늑대나 양일 경우         if(arr[x][y]=='v') wolf++;         else if(arr[x][y]=='o') sheep++;         while(!queue.isEmpty()) {             Pair t = queue.poll();                          for(int i=0;i<4;i++) {                 int tx = t.x+dir[i][0];                 int ty = t.y+dir[i][1];                 if(tx<0 || ty<0 || tx>=r || ty>=c) continue;                 if(visited[tx][ty]) continue;                 visited[tx][ty] = true;                 if(arr[tx][ty]=='#') continue;                 // 그 울타리 안의 늑대와 양 카운트                 if(arr[tx][ty]=='v') wolf++;                 else if(arr[tx][ty]=='o') sheep++;                 queue.add(new Pair(tx,ty));             }         }         // 울타리 안의 늑대와 양 수에따른 결과 계산         if(wolf>=sheep) tWolf+=wolf;         else tSheep+=sheep;     }          static class Pair{         private int x,y;         Pair(int x,int y){             this.x = x;             this.y = y;         }     } }