[백준] S2 3184번 양 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

3184번: 양

[문제] 

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

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

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

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

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

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

[입력]

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

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

[출력]

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

 

 

---

[풀이]

1. Map이 Char형으로 입력받아지므로 Char형 Map을 만들어준다.

2. 울타리 여부와 방문 여부를 판단하여 영역별 늑대와 양의 수를 DFS를 사용하여 구해준다.

3. 조건에 맞춰 해당 영역에 늑대의 수보다 양의 수가 많으면 늑대를 잡을 수 있기 때문에 이 조건에 맞춰 총 늑대와 양의 수를 구해준 후 출력한다.

[접근]

1. 각 공간을 탐색해야 하므로 DFS 혹은 BFS를 사용하면 되겠다고 생각하였다.

2. 각 공간의 양과 늑대의 수를 세고, 각 수를 비교해 총 수를 구해줘야 하므로, DFS 탐색을 하며 양과 늑대의 수를 구해준다.

3. DFS 탐색을 완료한 후 늑대와 양의 수를 비교해 결과에 반영해준다.

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int r, c;
	static char[][] map;
	static boolean[][] visited;
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};
	static int o = 0; // 각 영역을 탐색할때 쓸 양의 수
	static int v = 0; // 각 영역을 탐색할때 쓸 늑대의 수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int sheep = 0; // 정답으로 출력할 남아있는 양의 수
		int wolf = 0; // 정답으로 출력할 남아있는 늑대의 수

		StringTokenizer 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];

		// char로 쪼개서 map에 넣기
		for (int i = 0; i < r; i++) {
			String str = br.readLine();
			for (int j = 0; j < c; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (!visited[i][j] && (map[i][j] == 'o' || map[i][j] == 'v')) {
					// 매 탐색마다 새로 하므로 초기화
					o = v = 0;
					// dfs 탐색
					dfs(i, j);
					
					// 양이 늑대보다 많으면
					if(o > v)
						sheep += o; // 양을 증가
					else // 아니면
						wolf += v; // 늑대 증가
				}
			}
		}
		System.out.println(sheep + " " + wolf);
	}

	public static void dfs(int x, int y) {
		visited[x][y] = true; // 방문체크
		
		// 양이나 늑대일 경우 횟수 증가
		if (map[x][y] == 'v')
			v++;
		if (map[x][y] == 'o')
			o++;

		for (int i = 0; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];

			// 범위 벗어나거나 방문했거나 울타리라면
			if (nx < 0 || ny < 0 || nx >= r || ny >= c || visited[nx][ny] || map[nx][ny] == '#')
				continue;
			visited[nx][ny] = true; // 방문체크
			dfs(nx, ny);
		}
	}
}