[백준 1303번 C++] 전쟁-전투

 DFS 혹은 BFS로 풀 수 있는 문제다. 비슷한 백준 문제로는 단지번호 붙이기(2667), 토마토(7576)가 있다. https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

BFS/DFS문제에서 좌표에 관련된 문제를 풀이할 때 check point

1. 해당 매트릭스를 저장할 인접 리스트(혹은 인접 행렬)을 선언할 것.
2. 특정 좌표를 기점으로 주변을 탐색하는 문제의 경우 dx,dy 리스트를 선언할 것.
3. 좌표를 저장하는 큐의 경우 자료형을 Pair로 선언하여 x, y좌표를 모두 저장할 것.
   3-1.  큐에 첫번째 좌표를 추가한 뒤 for loop를 순회하며 조건에 맞는 좌표를 큐에 push.
   3-2.  더이상 큐에 넣을 좌표가 없을 때까지 while loop 실행.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

const int MAX = 101;
char map[MAX][MAX];
bool visited[MAX][MAX];

deque<pair<int,int>> Q;

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

int N, M;

int BFS(int x, int y) {
	int cnt = 1;
	Q.push_back({ x,y });
	visited[x][y] = true;

	while (!Q.empty()) {
		int xx = Q.front().first;
		int yy = Q.front().second;

		Q.pop_front();

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];
			if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
			if (visited[nx][ny] || map[nx][ny] != map[xx][yy]) continue;
			Q.push_back({ nx,ny });
			visited[nx][ny] = true;
			cnt++;
				//}
			//}
		}
	}
	return cnt*cnt;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> map[i];
	}

	int white_cnt = 0;
	int blue_cnt = 0;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				if(map[i][j]=='W') white_cnt+=BFS(i,j);
				else blue_cnt += BFS(i, j);
			}
		}
	}

	cout << white_cnt << ' ' << blue_cnt << "\n";

	return 0;
}

 

테스트 케이스는 잘 통과하는데 히든 테스트케이스에서 자꾸 막힌다. 예외사항을 잘 처리하고 if,for문 순회 꼼꼼히 확인할 것.