백준 1303 전쟁 - 전투 (c++) : 피너클

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

1303번: 전쟁 - 전투

dfs를 이용해 푼 문제다.

cin >> n >> m;
for (int i = 0; i < m; i++) {
	cin >> str[i];
}

memset(visited, false, sizeof(visited));

기본 세팅을 해준다.

int w = 0, b = 0;
for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
		if (!visited[i][j]) {
			if (str[i][j] == 'W') now = 'W';
			else now = 'B';

			int ans = dfs(i, j);
			
			if (now == 'W') w += ans * ans;
			else b += ans * ans;
		}
	}
}
cout << w << ' ' << b << endl;

int w와 b는 아군과 적군의 위력을 나타낸다.

모든 string을 돌며 만약 아직 방문하지 않은 정점이라면 뒤의 명령문을 실행한다.

먼저 아군인지 적군인지를 확인한뒤 now에 넣어준다. (now는 전역변수로 선언했다.)

그후 ans에 dfs(i, j)를 넣은후 w아니면 b에 제곱값을 넣어준다.

모든 과정을 마친후 w와 b를 출력해준다.

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

dfs에서 사용할 dx와 dy다. 현재 좌표에서 다음 좌표로 이동할때 사용할것이다.

int dfs(int y, int x) {
	visited[y][x] = true;

	int ans = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if (!visited[ny][nx] && str[ny][nx] == now) {
				ans += dfs(ny, nx);
			}
		}
	}
	return ans;
}

현재좌표인 y와 x를 전달받는다.

현재 위치의 visited를 true로 만들어주고 ans를 1로 선언해준다. 현재 위치를 방문했으니 시작하자마자 1이다.

현재 좌표에서 위, 아래, 양 옆으로 움직일수 있으니 for문을 이용해 확인해준다.

y에 dy[i]를 더해 다음 y좌표인 ny를 만들어주고 x에도 똑같이 해준다.

만약 ny와 nx가 string문안에 있고 방문하지 않았으며 현재 팀과 같은 팀이라면 ans에 dfs(ny, nx)를 더해준다.

모든 과정을 마친후 ans를 리턴해준다

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

int n, m;
string str[101];
bool visited[101][101];

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

char now;

int dfs(int y, int x) {
	visited[y][x] = true;

	int ans = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if (!visited[ny][nx] && str[ny][nx] == now) {
				ans += dfs(ny, nx);
			}
		}
	}
	return ans;
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> str[i];
	}

	memset(visited, false, sizeof(visited));

	int w = 0, b = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				if (str[i][j] == 'W') now = 'W';
				else now = 'B';

				int ans = dfs(i, j);

				if (now == 'W') w += ans * ans;
				else b += ans * ans;
			}
		}
	}
	cout << w << ' ' << b << endl;
}

전체코드다.