[백준] [3184] 양 (BFS) (JAVA)

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

3184번: 양

---

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

예제 입력 1 복사

6 6
...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###

예제 출력 1 복사

0 2

예제 입력 2 복사

8 8
.######.
#..o...#
#.####.#
#.#v.#.#
#.#.o#o#
#o.##..#
#.v..v.#
.######.

예제 출력 2 복사

3 1

예제 입력 3 복사

9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.

예제 출력 3 복사

3 5

---

※ JAVA 코드 (양)

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

public class Main {
	static int totalSheep, totalWolf;
	
	static int sheep, wolf;
	static int R, C;
	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();
			
			// 현재 큐에서 꺼낸 좌표
			int nowX = now.x;
			int nowY = now.y;
			
			// 양이면 양의 수 증가
			if(map[nowX][nowY] == 'o') sheep++;
			// 늑대면 늑대 수 증가
			if(map[nowX][nowY] == 'v') wolf++;
			
			
			for(int i = 0; i < 4; i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];
				
				if(nextX < 0 || nextY < 0 || nextX >= R || nextY >= C ||
				   visited[nextX][nextY] == true || map[nextX][nextY] == '#') {
					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);
			}
		}
		
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if(map[i][j] != '.' && visited[i][j] == false) {
					// 초기 양의 수와 늑대의 수를 0으로 초기화
					sheep = 0;
					wolf = 0;
					BFS(i, j);
					// 양의 수가 많으면 양의 수를 누적하고 아니면 더하지 않는다
					if(sheep > wolf) totalSheep += sheep;
					else totalWolf += wolf;
				}
			}
		}
		
		System.out.println(totalSheep + " " + totalWolf);
	}
}

---

※ 생각정리 (양)
양과 늑대의 최종 수와 각 필드별 수를 나누어 구하기 위해 총 4개의 변수를 선언하여 사용했다.

static int totalSheep, totalWolf;

static int sheep, wolf;

방문체크와 맵의 현재 좌표가 울타리인지를 판단하여 해당 좌표만 BFS탐색을 시행하였다.

BFS내부에서는 큐를 만들어 현재좌표와 다음에 이동할 좌표들을 큐에 담아가며 큐가 빌때까지 반복문을 돌렸고 큐가 비어서 빠져나올때에 양의 수와 늑대의 수를 비교하여 양의 수가 늑대의 수보다 많다면 양의 총 수를 담는 변수에 현재 울타리내의 양의 수를 더하였고 늑대의 수가 많거나 같을 경우에는 늑대의 총 수를 담는 변수에 현재 울타리내의 늑대 수를 더하였다.

 

BFS 알고리즘이 점점 응용되어 문제에 등장하고 있다. 사실 앞으로는 BFS와 DFS를 동시에 사용해야하는 문제들을 접해볼텐데 BFS응용을 잘 활용할 수 있게 되어 다행이라고 생각한다.

-새벽코딩-