Baekjoon 3184 양 JAVA

3184번: 양

문제

해당 문제는 map가 주어졌을 때 양과 늑대의 살아남은 수를 출력하는 문제다.

조건

'.'은 빈 필드, '#'은 울타리, 'v'는 늑대 'o'는 양을 의미한다.

이동은 상하좌우로 한 칸씩 이동 가능하며, 울타리로는 이동할 수 없고 연결된 모든 공간은 같은 영역으로 친다.

양이 늑대보다 많을 경우 늑대를 쫓아낼 수 있고, 늑대가 양과 같거나 많을 경우 양을 잡아먹을 수 있다.

풀이

해당 문제는 dfs를 이용했으며, 양과 늑대에 대한 큐를 선언해서 좌표 값을 담고 나중에 초기화해주는 방식으로 해결했다.

먼저 입력 처리를 하고 난 뒤, dfs를 돌려주며 dfs에서 현재 좌표값을 체크해 양 or 늑대인 경우 각각 큐에 담아주고 같은 영역을 모두 체크하고 나면 양과 늑대 큐 사이즈 비교를 통해 잡아먹히거나 쫓겨난 동물의 좌표를 초기화해주고 위와 같은 방식으로 map를 모두 탐색하고 난 뒤 다시 map를 탐색해서 살아남은 양과 늑대수를 카운트하여 출력해주었다.

문제를 다 풀고 생각해보니 굳이 큐를 사용하지 않고 int 변수를 통해 수를 카운트하고 비교하여 값을 경신하는 방식으로 진행하는 게 더 쉽게 해결하는 방법이라 생각이 들었다.

코드

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

public class Main {

	static int R, C, dy[]= {-1,1,0,0}, dx[]= {0,0,-1,1}, answ, anss;
	static char[][] map;
	static boolean[][] visit;
	static Queue<Node> sheep = new LinkedList<>(); //양 담는 큐
	static Queue<Node> wolf = new LinkedList<>(); // 늑대 담는 큐
	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]) { //방문안했고 울타리 아니면 방문
					dfs(i,j); //dfs를 이용해 갈수있는곳 다 탐방하면서 늑대 양 큐에 좌표 담기
					eat(); // 늑대큐와 양큐 크기비교를 통해 늑대 or 양을 잡아먹음
				}
			}
		}
		count(); // map를 방문하면서 살아남은 양과 늑대수 체크하고 출력
	}
	private static void count() { // map를 탐색하면서 카운트를 샌뒤 출력
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j] == 'v')
					answ++;
				else if(map[i][j] == 'o')
					anss++;
			}
		}
		System.out.println(anss + " "+ answ);
	}
	private static void eat() { // 큐 사이즈 비교를 통해 해당 좌표값을 초기화해줌
		if(wolf.size() >= sheep.size()) {
			while(!sheep.isEmpty()) {
				Node n = sheep.poll();
				map[n.y][n.x] = '.';
			}
			wolf.clear();
		}else {
			while(!wolf.isEmpty()) {
				Node n = wolf.poll();
				map[n.y][n.x] = '.';
			}
			sheep.clear();
		}
	}
	private static void dfs(int y, int x) {
		visit[y][x] = true;
		if(map[y][x] == 'v') // 현재 map값을 체크해서 양 또는 늑대일수도 있으니 담기
			wolf.add(new Node(y,x));
		else if(map[y][x] == 'o')
			sheep.add(new Node(y,x));
		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);
		}
	}
	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드