[백준] 1303 전쟁-전투 c++ 구현

 

목차

 

 

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

1303번: 전쟁 - 전투

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향 및 설명

이 문제는 연결리스트가 아닌 인접 행렬로 푸는 것이 더 유리하다.

 

출발 지점을  (0,0) 부터 (4,4) 까지 놓고 bfs를 실행하면 다음과 같이 방문한다.

-> 방문했던 곳은 탐색을 시작하지 않기 때문이다.

1	2	1	1	1
1	1	1	1	1
3	3	3	3	3
3	3	3	4	4
4	4	4	4	4

 

코드 구현

#include <iostream>
#include <queue>
#include<vector>
#include <cmath>

using namespace std;
//연결리스트로 구현한 bfs

int row, col, mycount=0, enemycount=0;
string arena[101][101]; 
bool visit[101][101];  //방문한 노드 표시용 배열

queue<pair<int, int>> q;

string team;
vector<int> xD = { 1, 0, -1, 0 };   //좌표 이동방향 설정
vector<int> yD = { 0, 1, 0, -1 };

void bfs(int y, int x) {
	
	int i, j;
	int count = 0;  //병사 수를 더해주기 위함
	
		visit[y][x] = true;

		q.push(make_pair(y, x));
		team = arena[y][x];

	//cout << "empty?" << q.empty() <<endl ;

	while (!q.empty()) {
		count++;  //병사 수를 더해줌
		int X = q.front().second;
		int Y = q.front().first;

		q.pop();
		for (i = 0; i < 4; i++) {   
			int x_ = X + xD[i];
			int y_ = Y + yD[i];   

			if (x_ >= 0 && x_ < row && y_ >= 0     //범위안에 있고 방문하지 않았고 같은 편일때 추가
				&& y_ < col && arena[y_][x_] == team && !visit[y_][x_]) {
				q.push(make_pair(y_, x_));
				visit[y_][x_] = true;
			}
		}
	}

	if (team == "W") { //우리 병사면 우리것에 제곱해 더해줌
		mycount += pow(count, 2);
	}
	else {
		enemycount += pow(count, 2);
	}

}


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

	int i, j;
	string s;
	cin >> row >> col;
	
	for (i = 0; i < col; i++) {
		cin >> s;
		for (j = 0; j < row; j++) {
			arena[i][j] = s.substr(j, 1);  
		}
	}

	for (i = 0; i < col; i++) {
		for (j = 0; j < row; j++) {
			if (!visit[i][j]) {    //방문하지 않았다면 bfs 실행
				bfs(i, j);
			}
			
		}
	}
	cout << mycount << " " << enemycount;
	

}

 

참고

https://wooono.tistory.com/410