#3187 : 양치기 꿍

풀이방법

사용된 것:

깊이우선탐색

 

2022.06.09

3184번 문제와 완전히 똑같은 문제이다.

양이 'o'가 아닌 'k'로 표시된다는 것만 다르다.

 

#3184 : 양

 

코드

Java(2022.06.09)

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

public class Main {
	
	
	static int r, c;	//마당의 크기
	static char[][] map;	//마당 지도
	static boolean[][] visited;	//방문여부 판별
	static int s, w;	//한 영역 안의 양(s)과 늑대(w)
	//아래는 상하좌우 좌표 계산에 쓰일 배열
	static int[] rchange = {-1, 1, 0, 0};
	static int[] cchange = {0, 0, -1, 1};
	
	
	//깊이우선탐색으로 영역의 양과 늑대 마릿수를 세는 함수
	static void dfs(int row, int col) {
		//해당 칸이 마당 밖이거나 이미 방문한 칸이거나 울타리이면 돌아가기
		if(row < 0 || row >= r || col < 0 || col >= c) return;
		if(visited[row][col]) return;
		if(map[row][col] == '#') return;
		
		//아래는 이외의 경우
		
		//일단 방문했다고 표시
		visited[row][col] = true;
		
		//해당 칸에 뭐가 있는지 확인
		if(map[row][col] == 'v') w++;	//늑대가 있다면 이 영역의 늑대 마릿수 1 증가
		else if(map[row][col] == 'k') s++;	//양이 있다면 이 영역의 양 마릿수 1 증가
		
		//상하좌우에 대하여 재귀
		for(int i = 0; i<4; i++) dfs(row + rchange[i], col + cchange[i]);
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		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);
			}
		}
		
		//정답을 저장할 변수 선언 및 0으로 초기화
		int sheep = 0;	//날이 밝았을 때 전체 양의 수
		int wolves = 0;	//날이 밝았을 때 전체 늑대의 수
		
		//모든 칸에 대하여 깊이우선탐색
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) {
				s = 0;	//이 칸이 속한 영역의 양 마릿수
				w = 0;	//이 칸이 속한 영역의 늑대 마릿수
				dfs(i,j);
				//이 영역에 양이 더 많다면 늑대를 없애고 그렇지 않다면 양을 없애기
				if(s>w) w = 0;
				else s = 0;
				//결과값을 정답에 반영
				sheep += s;
				wolves += w;
			}
		}
		
		//정답 출력
		System.out.print(sheep + " " + wolves);

	}

}