알고리즘(C++) / 백준 1303 : 전쟁 - 전투

1303

boj.kr/1303

1303번: 전쟁 - 전투

 

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

 

입력

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

 

출력

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

 

코드

//1303 전쟁-전투
#include<iostream>
#include<queue>
using namespace std;
int M, N;
char BW[101][101];
bool visited[101][101] = { false, };
int num;
const int dx[4] = { -1, 0, 1,0 }, dy[4] = { 0,1,0,-1 };

void DFS(int x, int y, char bw) {
	visited[x][y] = true; //방문 완료
	num++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= M || ny>= N)
			continue;
		if (visited[nx][ny] == false && BW[nx][ny] == bw) {
			DFS(nx, ny, bw);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
    
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> BW[i][j]; //입력
		}
	}

	int power_B = 0;
	int power_W = 0;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] != true) {
				num = 0;
				DFS(i, j, BW[i][j]);
				if (BW[i][j] == 'B') {
					power_B += num * num;
				}
				else if (BW[i][j] == 'W') {
					power_W += num * num;
				}
			}
		}
	}

	cout << power_W << " " << power_B << "\n";
	
	return 0;
}

 

설명

N과 M을 입력받는다. 여기서 N은 가로의 크기 M은 세로의 크기이다. 보통 배열과 반대로 입력받으므로 주의해야한다. 

BW배열에 병사들 B나 W를 입력받는다. 

visited는 방문되었을 때는 ture로 값을 변경해준다.

 

DFS는 시작 위치와 B또는 W를 입력받는다.

방문한 위치는 true로 변경해주고 다음 노드는 왼측, 아래, 우측, 위 순서로 방문한다. 방문한 노드가 존재하고 같은 병사라면 num을 증가시켜주고 존재하지 않는다면 반환한다. 

 

인접한 모든 노드를 방문하면 되기 때문에 DFS나 BFS를 이용하여 구할 수 있다. 나는 DFS를 이용하여 구현하였다. 

 

결과

 

고찰

출력이 잘되는데 틀린 결과가 나왔다. 그 이유가 가로와 세로의 입력을 잘못받았기 때문이다. 가로와 세로를 확인하여 입력받아주니 출력이 잘 나오는 것을 확인할 수 있었다.

 

난이도

●◐○○○