Baekjoon 3187 양치기 꿍 JAVA

3187번: 양치기 꿍

문제

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

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

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

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

 

조건

[입력]

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

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

 

[출력]

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

 

풀이

해당 문제는 map가 주어졌을 때 최종적으로 살아남는 늑대와 양의 수를 구하는 문제다.

dfs를 이용하여 해결했으며 로직은 아래와 같다.

1. 먼저 입력 처리를 한다.

2. map를 탐색하면서 벽이 아니고 방문하지 않았으면 dfs를 돌린다.

3. dfs에서 양과 늑대수를 갱신한다.

4. dfs가 끝나면 최종적으로 양과 늑대수를 갱신한다.

5. 출력한다.

 

코드

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

public class Main {

	static int R, C, ans_K, ans_V,  k, v, dy[]= {1,-1,0,0}, dx[]= {0,0,-1,1};
	static char[][] map;
	static boolean[][] visit;
	public static void main(String[] args) throws Exception{
		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];
		visit = new boolean[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++) {
				if(map[i][j] != '#' && !visit[i][j]) { //양 늑대수 체크하고 비교해서 최종값 갱신
					k = 0;
					v = 0;
					dfs(i,j);
					ans_K += k > v ? k : 0;
					ans_V += v >= k ? v : 0;
				}
			}
		}
		System.out.println(ans_K + " " + ans_V);
	}
	private static void dfs(int y, int x) {
		visit[y][x] = true; // 방문처리하고 양이나 늑대 수 증가시킴
		if(map[y][x] == 'v')
			v++;
		else if(map[y][x] == 'k') {
			k++;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y+ dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= R || nx >= C || map[ny][nx] == '#' || visit[ny][nx])
				continue;
			dfs(ny,nx);
		}
	}
}

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드