Notice
Recent Posts
Recent Comments
tony9402
[백준 10026] 적록색약 본문
반응형
백준 10026 적록색약
이 문제는 DFS 또는 BFS로 풀 수 있는 문제지만 둘 중에 하나로 두 번 돌려야 되는 문제이다. (두가지 풀이로 쓰기 귀찮아서 BFS 풀이만 올리겠다.)
먼저 BFS로 한 바퀴 돌릴 때 G인 곳을 R로 바꾸면서(R을 G로 바꿔도 상관없다) 색상에 의해 몇 구역으로 나뉘는지 체크를 하고 또 다시 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 | #include<cstdio> #include<cstring> #include<queue> using namespace std; queue<pair<int, int>> q; char map[101][101] = { 0 }; bool visit[101][101] = { 0 }; int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 }; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++)scanf("%s", map[i]); char temp; int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!visit[i][j]) { ans++; temp = map[i][j]; visit[i][j] = 1; if (temp == 'G')map[i][j] = 'R'; q.push(make_pair(i, j)); while (!q.empty()) { pair<int, int> now = q.front(); q.pop(); for (int k = 0; k < 4; k++) { if (!visit[now.first + dy[k]][now.second + dx[k]] && map[now.first + dy[k]][now.second + dx[k]] == temp) { visit[now.first + dy[k]][now.second + dx[k]] = 1; if (temp == 'G')map[now.first + dy[k]][now.second + dx[k]] = 'R'; q.push(make_pair(now.first + dy[k], now.second + dx[k])); } } } } } } printf("%d ", ans); ans = 0; for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)visit[i][j] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!visit[i][j]) { ans++; temp = map[i][j]; visit[i][j] = 1; q.push(make_pair(i, j)); while (!q.empty()) { pair<int, int> now = q.front(); q.pop(); for (int k = 0; k < 4; k++) { if (!visit[now.first + dy[k]][now.second + dx[k]] && map[now.first + dy[k]][now.second + dx[k]] == temp) { visit[now.first + dy[k]][now.second + dx[k]] = 1; q.push(make_pair(now.first + dy[k], now.second + dx[k])); } } } } } } printf("%d ", ans); return 0; } | cs |
반응형
'알고리즘 > Baekjoon Online Judge' 카테고리의 다른 글
[백준 2178] 미로탐색 (0) | 2018.08.21 |
---|---|
[백준 2606] 바이러스 (3) | 2018.08.17 |
[백준 1012번] 유기농 배추 (0) | 2018.08.16 |
[백준 2667번] 단지번호붙이기 (0) | 2018.08.16 |
백준 DFS/BFS 문제 (0) | 2018.08.15 |
Comments