[백준] [3187] 양치기 꿍 (BFS) (JAVA)

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

3187번: 양치기 꿍

---

문제

양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가?

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

입력

입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.

다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

출력

살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.

예제 입력 1 복사

6 6
...#..
.##v#.
#v.#.#
#.k#.#
.###.#
...###

예제 출력 1 복사

0 2

예제 입력 2 복사

8 8
.######.
#..k...#
#.####.#
#.#v.#.#
#.#.k#k#
#k.##..#
#.v..v.#
.######.

예제 출력 2 복사

3 1

예제 입력 3 복사

9 12
.###.#####..
#.kk#...#v#.
#..k#.#.#.#.
#..##k#...#.
#.#v#k###.#.
#..#v#....#.
#...v#v####.
.####.#vv.k#
.......####.

예제 출력 3 복사

3 5

---

※ JAVA 코드 (양치기 꿍)

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

public class Main {
	// 맵 크기
	static int R, C, s, w;
	static char[][] map;
	static boolean[][] visited;
	
	// 좌표이동
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	// 좌표를 담을 클래스
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void BFS(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		// 시작 좌표 큐에 입력
		q.offer(new Node(x, y));
		// 방문체크
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			// 큐의 현재 좌표
			Node now = q.poll();
			
			// 양
			if(map[now.x][now.y] == 'k') {
				s++;
			}
			if(map[now.x][now.y]== 'v') {
				w++;
			}
			
			for(int i = 0; i < 4; i++) {
				int nextX = now.x + dx[i];
				int nextY = now.y + dy[i];
				
				// 맵의 범위를 벗어나면 담지않는다
				if(nextX < 0 || nextY < 0 || nextX >= R || nextY >= C) {
					continue;
				}
				
				// 울타리가 있거나 이미 방문했을 경우 담지 않는다
				if(map[nextX][nextY] == '#' || visited[nextX][nextY] == true) {
					continue;
				}
				
				q.offer(new Node(nextX, nextY));
				visited[nextX][nextY] = true;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		// 맵의 크기
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		// 배열 초기화
		map = new char[R][C];
		visited = new boolean[R][C];
		
		// 맵 입력
		for(int i = 0; i < R; i++) {
			String input = br.readLine();
			for(int j = 0; j < C; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		int sheep = 0;
		int wolf = 0;
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				// 맵이 울타리가 아니고 아직 방문하지 않았다면
				if(map[i][j] != '#' && visited[i][j] == false) {
					s = 0;
					w = 0;
					BFS(i, j);
					// 카운트한 양과 늑대의 수를 비교하여 살아남은 생물을 추가
					if(s > w) {
						sheep += s;
					} else {
						wolf += w;
					}
				}
			}
		}
		// 출력
		System.out.println(sheep + " " + wolf);
	}
}

---

※ 생각정리 (양치기 꿍)

백준 양치기 꿍 문제는 입력받은 R, C 크기의 맵에서 한 울타리 영역 내부의 양(k)의 수와 늑대(v)의 수를 세어서 비교하여 살아남은 양과 늑대의 총 수를 구하는 문제이다.

먼저 맵에 값들을 입력 받는다. 

입력받은 맵을 탐색하는데 이때에 울타리인 좌표와 이미 방문한 좌표가 값에 들어왔을때는 탐색할 필요가 없다.

만약 입력값이 땅(.), 양(k), 늑대(v)일경우에만 탐색을 시작한다.

탐색동안에 양의 수와 늑대의 수를 전역변수 s, w에 담고 탐색이 끝났을 때 그 수를 비교하여 출력 변수에 담는다.

 

-새벽코딩-