Baekjoon 1303 전쟁 - 전투 JAVA

1303번: 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

조건

[입력]

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

[출력]

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

풀이

해당 문제는 dfs를 이용해 해결했다. 먼저 배열을 돌면서 방문했는지 체크하여주고 방문 안 했으면 해당 부분에서 부터 dfs를 돌려주고 최종적으로 증가된 cnt를 계산식에 맞춰 계산한 뒤 각 팀 변수에다 추가시켜주고 최종으로 출력을 해주면 된다.

전형적인 dfs 문제인 거 같다. 다만 해당 문제는 가로 세로를 체크를 잘해주어야 한다! 여기서 한번 틀림.

코드

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

public class Main {

	static int N, M, W, B, cnt, dy[]={-1,1,0,0}, dx[]= {0,0,-1,1};
	static boolean[][] visit;
	static char[][] map;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());  // N M 가로 세로 체크!!!!!!
		N = Integer.parseInt(st.nextToken()); 
		map = new char[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray(); // String를 char형 배열로 변환
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!visit[i][j]) { // 방문을 안했으면
					cnt = 0; // cnt 초기화하고
					dfs(i,j,map[i][j]); //dfs 돌림
					if(map[i][j] == 'W') // W, B에 따라 cnt 계산값을 추가
						W += cnt*cnt;
					else
						B += cnt*cnt;
				}
			} 
		}
		System.out.println(W +" "+ B);
	}
	private static void dfs(int i, int j, char c) {
		cnt++; // cnt 증가시킴 연결되어있는 칸 갯수
		visit[i][j] = true; // 방문 처리
		for (int k = 0; k < 4; k++) {
			int ny = i + dy[k];
			int nx = j + dx[k];
			if(ny < 0 || nx < 0 || ny >= N || nx >= M || visit[ny][nx] || map[ny][nx] != c) // 범위 벗어나거나 방문했거나 다른팀인경우 
				continue;
			dfs(ny,nx,c);
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드