백준 [10026] 적록색약

출처 : https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

1. c++

	#include<iostream>
	#include<cstring>
	using namespace std;
	char arr[101][101];
	bool isvisited[101][101];
	int cnt = 0;
	int dx[4] = { -1, 0, 0, 1 };
	int dy[4] = { 0, 1, -1, 0 };
	void dfs(int x, int y) {
	isvisited[x][y] = true;
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (!isvisited[nx][ny] && arr[x][y] == arr[nx][ny]) {
	dfs(nx, ny);
	}
	}
	return;
	}
	int main() {
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	cin >> arr[i][j];
	}
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (!isvisited[i][j]) {
	dfs(i, j);
	cnt++;
	}
	}
	}
	cout << cnt << " ";
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (arr[i][j] == 'G') arr[i][j] = 'R';
	}
	}
	memset(isvisited, false, sizeof(isvisited));
	cnt = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (!isvisited[i][j]) {
	dfs(i, j);
	cnt++;
	}
	}
	}
	cout << cnt << '\n';
	return 0;
	}

view raw 10026.cpp hosted with ❤ by GitHub

 

2. python

	from collections import deque
	N=int(input())
	arr = [[] for _ in range(N)]
	visited = [[False]*N for _ in range(N)]
	dx = [-1, 0, 1, 0]
	dy = [0, -1, 0, 1]
	cnt = 0
	for i in range(N):
	color = str(input())
	for x in color:
	arr[i].append(x)
	def bfs(x, y):
	dq=deque()
	dq.append([x, y])
	while dq:
	cur = dq.popleft()
	fir = cur[0]
	sec = cur[1]
	for i in range(4):
	nx = dx[i] + fir
	ny = dy[i] + sec
	if nx>=0 and ny>=0 and nx<N and ny<N :
	if visited[nx][ny] == False and arr[nx][ny] == arr[fir][sec]:
	visited[nx][ny] = True
	dq.append([nx, ny])
	for i in range(N):
	for j in range(N):
	if visited[i][j]==False:
	bfs(i, j)
	cnt+=1
	for i in range(N):
	for j in range(N):
	if arr[i][j]=='G':
	arr[i][j]='R'
	print(cnt)
	visited = [[False]*N for _ in range(N)]
	cnt=0
	for i in range(N):
	for j in range(N):
	if visited[i][j]==False:
	bfs(i, j)
	cnt+=1
	print(cnt)

view raw 10026.py hosted with ❤ by GitHub

상하좌우로 인정해 있는 경우 같은 구역에 속한다고 했으므로 dfs/bfs 사용하였음

적록색약이 아닌 경우 방문되지 않은 칸에 대해 bfs 돌려줌

적록색약인 경우를 구하기 위해 먼저 초록색 칸을 빨간색으로 바꿔줌

그 다음 visited 배열과 cnt 초기화해주고 적록색약인 경우도 방문되지 않은 칸에 대해 bfs 돌려줌