[BaekJoon] 1303 전쟁 - 전투

1.  문제 링크

2.  문제

요약

• 인접한 N명이 뭉쳐있을 때에 N^2의 위력을 낼 때, 흰색 옷의 병사와 파란색 옷의 병사들의 배치가 주어지면 흰색 옷의 병사들의 위력의 합과 파란색 옷의 병사들의 위력의 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 전쟁터의 가로 크기 N, 세로 크기 M이 주어지고 두 번째 줄부터 M개의 줄에는 (X, Y)에 있는 병사들의 옷색이 주어집니다.
• 출력: 첫 번째 줄에 흰색 옷 병사들의 위력의 합과 파란색 옷 병사들의 위력의 합을 출력합니다.

3.  소스코드

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

public class Main {
	static char[][] battlefield;
	boolean[][] visited;
	int[] soldierNum;
	int count;
	
	public void dfs(int x, int y, char team) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		soldierNum[count]++;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < battlefield.length && cy >= 0 && cy < battlefield[0].length) {	
				if(!visited[cx][cy] && battlefield[cx][cy] == team) {
					dfs(cx, cy, team);
				}
			}
		}
	}
	
	public int[] getSumOfPower() {
		if(battlefield.length == 1 && battlefield[0].length == 1) {
			if(battlefield[0][0] == 'W') {
				int[] sumOfPower = {1, 0};
				return sumOfPower;
			} else {
				int[] sumOfPower = {0, 1};
				return sumOfPower;
			}
		}
		int[] sumOfPower = new int[2];
		visited = new boolean[battlefield.length][battlefield[0].length];
		soldierNum = new int[battlefield.length * battlefield[0].length];
		for(int i = 0; i < battlefield.length; i++) {
			for(int j = 0; j < battlefield[i].length; j++) {
				if(!visited[i][j] && battlefield[i][j] == 'W') {
					count++;
					dfs(i, j, 'W');
				}
			}
		}
		for(int i = 0; i < soldierNum.length; i++) {
			if(soldierNum[i] != 0) {
				sumOfPower[0] += Math.pow(soldierNum[i], 2);
			}
		}
		count = 0;
		soldierNum = new int[battlefield.length * battlefield[0].length];
		for(int i = 0; i < battlefield.length; i++) {
			for(int j = 0; j < battlefield[i].length; j++) {
				if(!visited[i][j] && battlefield[i][j] == 'B') {
					count++;
					dfs(i, j, 'B');
				}
			}
		}
		for(int i = 0; i < soldierNum.length; i++) {
			if(soldierNum[i] != 0) {
				sumOfPower[1] += Math.pow(soldierNum[i], 2);
			}
		}
		return sumOfPower;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int row = Integer.parseInt(st.nextToken());
		int col = Integer.parseInt(st.nextToken());
		battlefield = new char[col][row];
		for(int i = 0; i < col; i++) {
			input = br.readLine();
			for(int j = 0; j < row; j++) {
				battlefield[i][j] = input.charAt(j);
			}
		}
		br.close();
		Main m = new Main();
		int[] result = m.getSumOfPower();
		bw.write(result[0] + " " + result[1] + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 dfs를 이용하여 인접한 병사들의 수를 구한 뒤에 이를 이용하여 각 병사들의 위력을 구할 수 있습니다.

1. 배치를 입력받고 만약 전쟁터의 크기가 1 * 1이라면 W일 때는 1 0 을 출력하고 B일 때는 0 1 을 출력합니다.
2. 전쟁터에서 해당 위치를 방문하였는지 확인하기 위해 visited 배열을 만들고 인접한 병사들의 수를 저장하기 위해 soldierNum 배열을 만들며 인접한 병사들의 집합의 번호를 나타내는 count 변수를 만듭니다.
3. 전쟁터의 전체 위치를 돌면서 인접한 흰색 옷 병사들의 수를 구하고 그 이후에 인접한 파란색 옷 병사들의 수를 구합니다.

• 해당 위치가 아직 방문되지 않았고 해당 위치가 찾고 있는 색깔이라면 dfs를 실행합니다.

1. 해당 위치에서 상하좌우를 확인하기 위해 dx, dy 배열을 만들고 해당 위치를 방문했기 때문에 visited에서 해당 위치를 true로 변경하며 해당 위치에 병사가 존재하므로 count번째의 soliderNum의 수를 1 늘립니다.
2. 상하좌우를 하나씩 확인하며 해당 위치가 전쟁터 내에 존재하고 즉 (0, 0)에서 (M - 1, N - 1) 사이에 존재하고 해당 위치를 아직 방문하지 않았으며 해당 위치에 지금 찾고 있는 색의 병사가 존재한다면 재귀를 통해 해당 위치에서의 상하좌우를 확인합니다.