답안

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

public class Main {
	static char[][] map;
	static boolean[][] visited;
	static int gom, binky;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) {
		int h = 12;
		int w = 8;

		String[] board = {".######.", "#.oo...#", "#.######", "#.##vv.#", "#v##o###", "#####o##",
							"#ovo#v##", "#.o#v.##", "###v####", "###v#oo#", "##..####", ".#######"};

		int[] answer = solution(h, w, board);
		System.out.println(answer[0] + " " + answer[1]);
		System.out.println(answer[2]);
	}

	public static int[] solution(int h, int w, String[] board) {
		int[] answer = new int[3];
		gom = 0;
		binky = 0;

		map = new char[h][w];
		visited = new boolean[h][w];

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				map[i][j] = board[i].charAt(j);
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] != '#' && !visited[i][j]) {
					bfs(i, j, h, w);
				}
			}
		}
		
		answer[0] = gom;
		answer[1] = binky;

		if (binky < gom) {
			answer[2] = 1;
		}
		else if (binky > gom) {
			answer[2] = -1;
		}
		else {
			answer[2] = 0;
		}
		return answer;
	}

	public static void bfs(int x, int y, int h, int w) {
		Queue<Location> queue = new LinkedList<Location>();
		visited[x][y] = true;
		queue.add(new Location(x, y));

		int g = 0;
		int b = 0;
		
		if (map[x][y] == 'o') {
			g++;
		}
		else if (map[x][y] == 'v') {
			b++;
		}
		
		while (!queue.isEmpty()) {
			Location loc = queue.poll();
			int loc_x = loc.x;
			int loc_y = loc.y;
			
			for (int i = 0; i < 4; i++) {
				int nx = loc_x + dx[i];
				int ny = loc_y + dy[i];
				
				if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
					if (map[nx][ny] != '#' && !visited[nx][ny]) {
						visited[nx][ny] = true;
						queue.add(new Location(nx, ny));
						
						if (map[nx][ny] == 'o') {
							g++;
						}
						else if (map[nx][ny] == 'v') {
							b++;
						}
					}
				}
			}
		}
		
		if (g != 0 || b != 0) {
			if (g > b) {
				gom++;
			}
			else {
				binky++;
			}
		}
	}
}

class Location {
	int x;
	int y;

	public Location(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

1. 문제 파악

1. 영역은 울타리로 나뉘게 되고 게임판에는 여러 영역이 있습니다.

2. 영역 내에서의 소울곰과 빙키 캐릭터 수를 세기 위해서 BFS를 이용합니다.

3. 캐릭터는 수직과 수평으로만 이동할 수 있기 때문에 대각선 방향은 고려하지 않아도 됩니다.

4. 캐릭터의 수를 비교해 게임의 승패를 결정합니다.

2. 풀이

1. 게임판이 String 배열로 주어졌기 때문에 캐릭터와 울타리를 구분하기 위해서 char형 이차원 배열로 바꿔줍니다.

for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
				map[i][j] = board[i].charAt(j);
		}
}

 

2. 반복문을 돌면서 모든 정점을 확인합니다. 울타리가 아니고 아직 방문하지 않는 정점이라면 BFS 탐색을 시작합니다.

for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
				if (map[i][j] != '#' && !visited[i][j]) {
					bfs(i, j, h, w);
				}
		}
}

 

3. BFS 탐색을 위해서 큐를 선언합니다. 탐색을 시작하는 정점이 빙키 혹은 소울곰 캐릭터일 수 있기 때문에 조건문을 통해서 확인합니다.

if (map[x][y] == 'o') {
		g++;
}
else if (map[x][y] == 'v') {
		b++;
}

 

4. BFS 탐색을 합니다. 또한, 문제의 목표가 빙키와 소울곰의 캐릭터 수 차이를 알아내 승패를 결정하는 것이므로 3번과 같이 조건문을 통해 캐릭터의 수를 카운트합니다.

if (map[nx][ny] != '#' && !visited[nx][ny]) {
				visited[nx][ny] = true;
				queue.add(new Location(nx, ny));
						
				if (map[nx][ny] == 'o') {
						g++;
				}
				else if (map[nx][ny] == 'v') {
						b++;
				}
}

 

5. 영역 내에 소울곰과 빙키 캐릭터가 모두 존재하지 않을 수도 있으므로, 소울곰과 빙키 캐릭터 중 하나의 캐릭터가 0이 아닐 때의 조건을 추가해서 해당 영역 내의 승패를 결정합니다.

if (g != 0 || b != 0) {
		if (g > b) {
				gom++;
		}
		else {
				binky++;
		}
}

 

6. 다시 메인함수로 돌아와서 최종 승패를 결정합니다.