[BaekJoon] 백준 10026번 적록색약 - C++, Python

 

[BaekJoon] 백준 10026번 적록색약

 

문제: https://www.acmicpc.net/problem/10026

 

 

내코드

 

- 간단하게 bfs를 이용하는 문제

- 두 예제를 돌려야되서 초기화에 신경을 써줘야했다.

- 아래는 아이패드에 정리한 내용

 

백준 10026번 적록색약.pdf

2.41MB

 

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int n = 0;
int arr[100][100] = { 0, };
int arr2[100][100] = { 0, };
queue <pair<int, int>> qu;
int res = 0;
bool visited[100][100] = { false, };
pair<int, int> cur;

void isNear(int x, int y, int rgb[100][100]) {
	if (x < 0 || y < 0 || x >= n || y >= n) return;
	if (visited[x][y] == false && rgb[x][y] == rgb[cur.first][cur.second]) {
		qu.push(make_pair(x, y));
		visited[x][y] = true;
	}
}

void bfs(int rgb[100][100]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
		}
	}
	res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0;j < n; j++) {
			if (visited[i][j]) continue;
			qu.push(make_pair(i, j));
			visited[i][j] = true;
			res++;
			while (!qu.empty()) {
				cur = qu.front();
				qu.pop();
				int a = cur.first;
				int b = cur.second;
				isNear(a + 1, b, rgb);
				isNear(a, b - 1, rgb);
				isNear(a, b + 1, rgb);
				isNear(a - 1, b, rgb);
			}
		}
	}
	cout << res << " ";
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char tmp;
			cin >> tmp;
			if (tmp == 'R') {
				arr[i][j] = 0;
				arr2[i][j] = 0;
			}
			else if (tmp == 'G') {
				arr[i][j] = 1;
				arr2[i][j] = 0;
			}
			else if (tmp == 'B') {
				arr[i][j] = 2;
				arr2[i][j] = 2;
			}
		}
	}
	bfs(arr);
	bfs(arr2);
	return 0;
}

 

 

2022/10/11 다시 품

from collections import deque


def bfs(arr):
    global N

    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    area = 0
    visited = [[False for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if visited[i][j]:
                continue

            visited[i][j] = True
            area += 1
            queue = deque([[i, j]])

            while queue:
                value = queue.popleft()

                for k in range(4):
                    nx = value[0] + dx[k]
                    ny = value[1] + dy[k]

                    if nx < 0 or ny < 0 or nx >= N or ny >= N:
                        continue
                    if visited[nx][ny] or arr[nx][ny] != arr[value[0]][value[1]]:
                        continue

                    visited[nx][ny] = True
                    queue.append([nx, ny])
    return area


N = int(input())
a = [["" for _ in range(N)] for _ in range(N)]
b = [["" for _ in range(N)] for _ in range(N)]

for i in range(N):
    tmp = list(input())
    for j in range(len(tmp)):
        a[i][j] = tmp[j]
        if tmp[j] == "G":
            b[i][j] = "R"
        else:
            b[i][j] = tmp[j]

print(str(bfs(a)) + " " + str(bfs(b)))