[백준] [1303] 전투 (BFS) (JAVA)

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

---

 

2 초

128 MB

10318

3990

3198

37.770%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1 복사

130 65

---

※ JAVA 코드 (전투)

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, W, B;
	
	static char[][] map;
	static boolean[][] visited;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	// 좌표를 탐색할 클래스
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	// 너비 우선 탐색
	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y));
		visited[x][y] = true;
		
		double manCount = 1;
		
		// 현재 탐색중인 병사가 아군인지 적군인지
		char currentMan = map[x][y];
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nextX = now.x + dx[i];
				int nextY = now.y + dy[i];
				
				// 맵의 크기를 벗어나면 담지않는다.
				if(nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
					continue;
				}
				
				// 이미 방문한 곳이나 적군은 담지 않는다.
				if(visited[nextX][nextY] == true || map[nextX][nextY] != currentMan) {
					continue;
				}
				
				// 탐색할 좌표를 큐에 담고 방문체크
				q.offer(new Node(nextX, nextY));
				visited[nextX][nextY] = true;
				// 병사의 수
				manCount++;
			}
		}
		
		// 현재 붙은 병사 수의 제곱
		if(currentMan == 'W') {
			W += Math.pow(manCount, 2);
		} else {
			B += Math.pow(manCount, 2);
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		W = 0;
		B = 0;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new char[M][N];
		visited = new boolean[M][N];
		
		for(int i = 0; i < M; i++) {
			String input = br.readLine();
			for(int j = 0; j < N; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				// 방문하지 않았으면 탐색시작
				if(visited[i][j] == false) {
					bfs(i, j);
				}
			}
		}
		
		System.out.println(W + " " + B);
	}
}

---

※ 생각정리 (전투)

1. 처음 입력받은 N, M은 각각 가로길이, 세로길이 이기때문에 맵을 입력받을 때 M을 먼저 N을 나중에 받아야한다.

for(int i = 0; i < M; i++) {
    String input = br.readLine();
    for(int j = 0; j < N; j++) {
        map[i][j] = input.charAt(j);
    }
}

2. 반복문을 돌려 현재 좌표가 방문하지 않은 곳이라면 탐색을 돌린다.

for(int i = 0; i < M; i++) {
    for(int j = 0; j < N; j++) {
        // 방문하지 않았으면 탐색시작
        if(visited[i][j] == false) {
            bfs(i, j);
        }
    }
}

3. 현재 탐색에 들어온 좌표의 병사가 아군인지 적군인지 담으며 카운트는 1을 담는다.

double manCount = 1;
		
// 현재 탐색중인 병사가 아군인지 적군인지
char currentMan = map[x][y];

4. 탐색이 끝났으면 아군과 적군을 나누어 제곱수를 담는다.

// 현재 붙은 병사 수의 제곱
if(currentMan == 'W') {
    W += Math.pow(manCount, 2);
} else {
    B += Math.pow(manCount, 2);
}

5. 아군과 적군을 공백을 사이에 두고 출력한다.

 

-새벽코딩-