백준 3184번 : 양

 문제

www.acmicpc.net/problem/3184

3184번: 양

3184 양

 

 구현 방법

 bfs로 구현하였습니다.

입력을 완료한 후 울타리 공간이 1, 그 공간에 늑대나 양이 있을 수 있으므로 '#'가 아닐 때만 탐색하게 해주었습니다.

탐색을 하면서 '#'가 아닐 때 이동을 해주고 이동한 곳이 양이나 늑대이면 각자의 카운팅을 올려주었습니다.

울타리 내 한 공간의 탐색이 끝난 후 늑대 카운트와 양 카운트를 비교한 후 늑대의 수가 양보다 크면 늑대의 값을 추가, 양이 더 크면 양의 값을 추가하여 출력해주었습니다.

 

 구현 코드

package BOJ.silver;

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

public class B3184_양 {
	static int R, C, wolf, sheep, ansW, ansS;
	static char[][] map;
	static int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<rc> bfs;
	static class rc {
		int r, c;

		public rc(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	public static void main(String[] args) throws IOException {
		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];
		bfs = new LinkedList<>();
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			map[r] = input.toCharArray();
		}
		// 입력 완료
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]!='#') {
					sheep=0; wolf =0;
					if (map[r][c]=='o') sheep++;
					else if (map[r][c]=='v') wolf++;
					bfs.offer(new rc(r, c));
					map[r][c]='#';
					bfsL();
				}
			}
		}
		System.out.println(ansS+" "+ansW);
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			int size = bfs.size();
			for (int i=0;i<size;i++) {
				rc now = bfs.poll();
				for (int d=0;d<4;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr,nc) && map[nr][nc]!='#') {
						if (map[nr][nc]=='o') sheep++; // 양이면 양 카운트++
						else if (map[nr][nc]=='v') wolf++; // 늑대면 늑대 카운트++
						map[nr][nc]='#';
						bfs.offer(new rc(nr, nc));
					}
				}
			}
		}
		if(sheep<=wolf) ansW += wolf; // 늑대의 수가 양보다 크거나 같으면 늑대 값 더해주기
		else ansS += sheep;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!