[백준 알고리즘]/[C++]
1303번 전쟁-전투 | BFS, DFS | Baekjoon BOJ 백준 1303 C++ 코드
말하는펭귄
2021. 2. 11. 20:03
728x90
반응형
이번 포스팅은 백준 1303번 전쟁-전투입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
기본 알고리즘
BFS 너비 우선 탐색
DFS 깊이 우선 탐색
더보기
문제를 읽자!
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다.
전체 코드
BFS 너비 우선 탐색
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
int N, M;
const int MAX = 101;
char input[MAX][MAX];
int map[MAX][MAX] = { 0, };
bool visited[MAX][MAX] = { 0, };
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,-1,1 };
int wSum = 0; //W병사 위력 합
int bSum = 0; //B병사 위력 합
int s = 1; //뭉친 병사 수
queue<pair<int, int>> q;
void BFS(int y, int x) {
visited[y][x] = true;
q.push(make_pair(y, x));
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= M || nx >= N)
continue;
if (map[ny][nx] == 1 && visited[ny][nx] == 0) {
visited[ny][nx] = true;
s++;
q.push(make_pair(ny, nx));
}
}
}
}
void reset() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
visited[i][j] = 0;
map[i][j] = 0;
}
}
}
int main() {
cin >> N >> M;
/*입력 받기*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
scanf("%1s", &input[i][j]);
}
}
/*W=1, B=0로 변환하여 map에 저장*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == 'W') {
map[i][j] = 1;
}
}
}
/*W의 BFS*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1 && visited[i][j] == 0) {
BFS(i, j);
wSum += s * s;
s = 1;
}
}
}
/*map, visited 초기화*/
reset();
/*B=1, W=0로 변환하여 map에 저장*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == 'B') {
map[i][j] = 1;
}
}
}
/*B의 BFS*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1 && visited[i][j] == 0) {
BFS(i, j);
bSum += s * s;
s = 1;
}
}
}
cout << wSum << " " << bSum;
}
|
cs |
DFS 깊이 우선 탐색
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int N, M;
const int MAX = 101;
char input[MAX][MAX];
int map[MAX][MAX] = { 0, };
bool visited[MAX][MAX] = { 0, };
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,-1,1 };
int wSum = 0; //W병사 위력 합
int bSum = 0; //B병사 위력 합
int s = 1; //뭉친 병사 수
void DFS(int y, int x) {
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= M || nx >= N)
continue;
if (map[ny][nx] == 1 && visited[ny][nx] == 0) {
visited[ny][nx] = true;
s++;
DFS(ny, nx);
}
}
}
void reset() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
visited[i][j] = 0;
map[i][j] = 0;
}
}
}
int main() {
cin >> N >> M;
/*입력 받기*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
scanf("%1s", &input[i][j]);
}
}
/*W=1, B=0로 변환하여 map에 저장*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == 'W') {
map[i][j] = 1;
}
}
}
/*W의 DFS*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1&&visited[i][j]==0) {
DFS(i, j);
wSum += s * s;
s = 1;
}
}
}
/*map, visited 초기화*/
reset();
/*B=1, W=0로 변환하여 map에 저장*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == 'B') {
map[i][j] = 1;
}
}
}
/*B의 BFS*/
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1 && visited[i][j] == 0) {
DFS(i, j);
bSum += s * s;
s = 1;
}
}
}
cout << wSum << " " << bSum;
}
|
cs |
728x90
반응형