[BOJ] 3184.양(DFS,BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

완탐 기본 문제다.

양이 이기면 좋겠다는 순수한 마음으로 풀었다.

울타리로 둘러쌓인 구역들을 탐색하는데

늑대를 발견하면 늑대의 수를 count,

양을 발견하면 양의 수를 count 해주고,

해당 구역의 탐색을 모두 마쳤으면,

해당 구역 내에서 이긴 동물의 수를 최종적으로 result양 또는 result늑대 변수에 누적해주면 된다.

#. Code_bfs

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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ3184 {       static int O, V, R, C;     static char[][] map;     static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};     static class Point {         int r, c;           public Point(int r, int c) {             super();             this.r = r;             this.c = c;         }              }          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());         map = new char[R][C];         for (int i = 0; i < R; i++)              map[i] = br.readLine().toCharArray();                  for (int i = 0; i < R; i++) {             for (int j = 0; j < C; j++) {                 // 울타리일경우 pass                 if(map[i][j] == '#') continue;                 // 울타리가 아니면 해당 영역을 확인해보자.                 Find(i, j);             }         }                  System.out.println(O + " " + V);     }       private static void Find(int r, int c) {                  int cntO = 0, cntV = 0;         Queue<Point> q = new LinkedList<>();         // 시작점이 늑대라면         if(map[r][c] == 'o') cntO++;         // 시작점이 양이라면         if(map[r][c] == 'v') cntV++;                  map[r][c] = '#';         q.add(new Point(r, c));         // 울타리로 채우면서 양의 수와 늑대의 수를 센다         while(!q.isEmpty()) {             Point now = q.poll();                          for (int d = 0; d < 4; d++) {                 int rr = now.r + dr[d];                 int cc = now.c + dc[d];                 // 범위를 벗어날 경우                 if(rr < 0 || cc < 0 || cc >= C || rr >= R) continue;                 // 울타리가 있을 경우                 if(map[rr][cc] == '#') continue;                                  // 늑대라면                 if(map[rr][cc] == 'o') cntO++;                 // 양이라면                 if(map[rr][cc] == 'v') cntV++;                 // 울타리로 변경                 map[rr][cc] = '#';                 // 다음 좌표를 Queue에 넣어주기                 q.add(new Point(rr, cc));             }         }                  // 양의 수가 더 많으면 양이 살아남고,         // 늑대 수가 더 많으면 늑대가 살아남는다.         if(cntO > cntV) O += cntO;         else V += cntV;     }   }   Colored by Color Scripter

cs

#. Code_dfs

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 73 74

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ3184_dfs {       static int O, V, R, C, cntO, cntV;     static char[][] map;     static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};     static class Point {         int r, c;           public Point(int r, int c) {             super();             this.r = r;             this.c = c;         }              }          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());         map = new char[R][C];         for (int i = 0; i < R; i++)              map[i] = br.readLine().toCharArray();                  for (int i = 0; i < R; i++) {             for (int j = 0; j < C; j++) {                 // 울타리일경우 pass                 if(map[i][j] == '#') continue;                 // 울타리가 아니면 해당 영역을 확인해보자.                 cntO = cntV = 0;                 Find(i, j);                 // 양의 수가 더 많으면 양이 살아남고,                 // 늑대 수가 더 많으면 늑대가 살아남는다.                 if(cntO > cntV) O += cntO;                 else V += cntV;             }         }                  System.out.println(O + " " + V);     }       // 울타리로 채우면서 양의 수와 늑대의 수를 센다     private static void Find(int r, int c) {                  // 늑대라면         if(map[r][c] == 'o') cntO++;         // 양이라면         if(map[r][c] == 'v') cntV++;         map[r][c] = '#';           for (int d = 0; d < 4; d++) {             int rr = r + dr[d];             int cc = c + dc[d];             // 범위를 벗어날 경우             if(rr < 0 || cc < 0 || cc >= C || rr >= R) continue;             // 울타리가 있을 경우             if(map[rr][cc] == '#') continue;                          Find(rr, cc);         }     }   }   Colored by Color Scripter

cs