Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- HTML #CSS
- 컴퓨터공학 #자료구조 #스택 #c++ #알고리즘 #백준문제풀이
- 컴퓨터공학 #c #c언어 #문자열입력
- 잔
- BOJ #컴퓨터공학 #C++ #알고리즘 #자료구조
- 컴퓨터공학 #Java #자바 #클래스 #객체 #인스턴스
Archives
- Today
- Total
영벨롭 개발 일지
[백준 BOJ][C++]3187번 양치기 꿍 풀이: BFS/DFS 본문
https://www.acmicpc.net/problem/3187
이 문제는 BFS/DFS 를 사용하여 해결할 수 있습니다.
[풀이 과정]
1. R과 C, 각 영역에 대한 정보 입력
2. 영역이 'k'라면 전체 양의 수를 나타내는 k값 증가, 'v'라면 전체 늑대 수를 나타내는 v값 증가
3. 아직 방문하지 않은 울타리로 둘러쌓인 영역 탐색(bfs)
4. 탐색 과정에서 울타리로 둘러쌓인 영역 내에서의 양의 수(knum), 늑대의 수(vnum) set
5. 탐색이 끝나면 두 수를 비교해서 전체 양의수와 전체 늑대 수 reset
6. 전체 영역 탐색할 때까지, 3~5과정 반복
전체 코드입니다.
#include<iostream>
#include <string>
#include <vector>
#include<queue>
using namespace std;
int r, c;
int v, k;
char map[250][250];
bool visit[250][250] = { false, };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
void bfs(int x, int y) {
int vnum = 0;
int knum = 0;
queue<pair<int, int>> q;
visit[y][x] = true;
q.push({ x, y });
while (!q.empty()) {
int cx = q.front().first;
int cy = q.front().second;
if (map[cy][cx] == 'k')
knum++;
else if (map[cy][cx] == 'v')
vnum++;
q.pop();
for (int i = 0; i < 4; i++) {
int tx = cx + dx[i];
int ty = cy + dy[i];
if (tx < 0 || tx >= c || ty < 0 || ty >= r)
continue;
if (visit[ty][tx] || map[ty][tx] == '#')
continue;
visit[ty][tx] = true;
q.push({ tx, ty });
}
}
if (vnum >= knum) {
k -= knum;
}
else {
v -= vnum;
}
}
int main(void) {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> map[i][j];
if (map[i][j] == 'v')
v++;
else if (map[i][j] == 'k')
k++;
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (!visit[i][j] && map[i][j] != '#') {
bfs(j, i);
}
}
}
cout << k << " " << v;
return 0;
}
반응형
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[백준 BOJ][C++]11057번 오르막 수 풀이: DP (0) | 2022.03.10 |
---|---|
[백준 BOJ][C++]1149번 RGB 거리 풀이: DP (0) | 2022.03.10 |
[백준 BOJ][C++]2225번 합분해 풀이: DP (0) | 2022.03.09 |
[백준 BOJ][C++]1912번 연속 합 풀이: DP (0) | 2022.03.06 |
[백준 BOJ][C++]1699번 제곱수의 합 풀이: DP (0) | 2022.03.06 |