백준 3184번 : 양

1. #으로 둘러싸인 곳이 우리이다.

2. 우리 안에서 늑대인 v와 o인 양을 비교하는데, 우리 안에 늑대가 많으면 늑대의 수를, 양이 많으면 양의 수를 가져온다.

3. 모든 우리 안에 남은 늑대와 양의 수를 가져온다.

 

문제를 간단하게 위의 3가지 순서로 표현할 수 있다.

 

딱 보자마자 bfs로 풀면 되겠다는 생각이 들었다.

 

1. #이 아니고 ,갔다온 지점이 아니면 그 우리를 확인한다. (BFS 함수를 부른다.)

2. 빈 칸이거나 동물일 경우, 옆에 붙어있는 칸들을 모두 확인해서 우리 안이 맞으면 큐에 넣어준다. 

 - 동시에, 동물일 경우엔 해당 동물의 카운트를 증가시킨다.

3. 해당 우리를 모두 검사했다면, 해당 우리에서 점령한 동물의 수를 카운트해준다.

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static String arr[][];
	static Boolean visited[][];
	static int r;
	static int c;
	static int totalSheepCnt = 0;
	static int totalWolfCnt = 0;

	static int sheepCnt = 0;
	static int wolfCnt = 0;
	
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		c = sc.nextInt();
		arr = new String[r+1][c+1];
		visited = new Boolean[r+1][c+1];
		
		for(int i=1;i<=r;i++) {
			String str = sc.next();
			for(int j=1;j<=str.length();j++) {
				arr[i][j] = str.charAt(j-1)+"";
				visited[i][j] = false;
			}
		}
	
		for(int i=1;i<=r;i++) {
			for(int j=1;j<=c;j++) {
				if(!arr[i][j].equals("#") && !visited[i][j]) {
					bfs(i,j);
					if(wolfCnt >= sheepCnt) {
						totalWolfCnt += wolfCnt;
					} else {
						totalSheepCnt += sheepCnt;
					}
					wolfCnt =0;
					sheepCnt = 0;
				}
				// 1. bfs로 #이 아닌 부분을 모두 넣는다.
				//    동시에 v와 o의 수를 센다.
				// 나왔을 때,vSC > oSC 를 파악해서total 값 갱신 
				// 2. 위의 과정을 모든 flase 될때까지 쭈루륵간다.
			}
		}
		System.out.println(totalSheepCnt + " "+totalWolfCnt);
	}

	
	public static void bfs(int i,int j) {
		int dx[] = {1,0,-1,0};
		int dy[] = {0,1,0,-1};
		Queue<Point> queue = new LinkedList<Point>();
		
		Point point = new Point(i,j);
		
		 if(arr[i][j].equals("v")) {
				wolfCnt++;
		} else if(arr[i][j].equals("o")) {
				sheepCnt++;
		}
		
		queue.add(point);
		visited[i][j] = true;
		while(!queue.isEmpty()) {
			int topX = queue.peek().x;
			int topY = queue.peek().y;
			visited[topX][topY] = true;
			for(int idx=0;idx<4;idx++) {
				int curX=topX+dx[idx];
				int curY=topY+dy[idx];
				if(curX>0 &&curX<=r && curY>0&& curY<=c && !visited[curX][curY]) {
					if(arr[curX][curY].equals("#")) {
						continue;
					} else if(arr[curX][curY].equals("v")) {
						wolfCnt++;
					} else if(arr[curX][curY].equals("o")) {
						sheepCnt++;
					}
				
					visited[curX][curY] = true;
					Point p = new Point(curX, curY);
					queue.add(p);
				}
			}
			queue.remove();
		}
	}
}

class Point{
	int x;
	int y;
	
	Point(int a, int b) {
		this.x = a;
		this.y = b;
	}
 
}

 

 * 코드가 복잡하지만, Point는 사용하지 않아도 풀 수 있는 문제이다.

 

여기서 포인트는 아래와 같다고 생각한다.

 - dx,dy 배열을 이용해 양옆을 확인하는 것.

 - bfs 를 이용해서 푸는 것.

 

하지만, 위의 문제는 dfs를 이용해서 구현하는 것도 가능하다.

어차피 dfs도 완전 탐색이기 때문에 dfs를 사용하더라도 구현이 불가한 건 아니다. 게다가 재귀를 이용할 수 있어서 코드가 간편하기도 하다.

 

또한, 더욱 가독성있고 간단하게 구현하려면, visited 배열을 사용하지 않아도 된다. 

이미 갔다온 지점을 x 등, 다른 표시로 추가한다면, 굳이 visited 배열을 만들지 않아 메모리를 조금 덜 쓸 수 있다.