[C] 백준 - 10026번: 적록색약

10월 18일(수) - 그래프와 순회 (10026번)

10026번: 적록색약

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 기본적인 dfs 방식의 그래프 문제라고 판단

- 하지만 정상 / 색약인 경우로 나누어서 dfs 를 각각 진행해야하기에, dfs 함수를 2개 작성해야할듯

 

- 입력으로 R,G,B가 들어오게되므로 string을 통해서 입력받는다

- R이면 arr[ ][ ] = 1, G이면 arr[ ][ ] = 2, B이면 arr[ ][ ] = 3으로 나누어서 표현하며

  1) 정상인 경우, 각각의 색깔별 숫자를 dfs의 매개변수에도 추가하여 활용한다

  이때 색깔별로 변수 red, green, blue에 등장횟수를 카운팅한다

  2) 적록색약인 경우, 카운팅하기 위해서 R과 G를 or 조건으로 묶고, 적록색약인 경우의 dfs를 진행한다

  이때는 R과 G를 묶어서 변수 red_green으로 카운팅한다

- 출력은

  정상 = red + green + blue의 합을 출력하고

  색약 = red_green + blue의 합을 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

int N;
int arr[101][101];
int visited[101][101];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void dfs(int y, int x, int color)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
		{
			continue;
		}
		if (arr[next_y][next_x] == color && visited[next_y][next_x] == 0)
		{
			dfs(next_y, next_x, color);
		}
	}
}

void red_green_blind(int y, int x)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
		{
			continue;
		}
		if ((arr[next_y][next_x] == 1 || arr[next_y][next_x] == 2) && visited[next_y][next_x] == 0)
		{
			red_green_blind(next_y, next_x);
		}
	}
}

int main(void)
{
	scanf("%d", &N);

	char string[101];
	for (int i = 0; i < N; i++)
	{
		scanf("%s", string);

		for (int j = 0; j < N; j++)
		{
			if (string[j] == 'R')
			{
				arr[i][j] = 1;
			}
			else if (string[j] == 'G')
			{
				arr[i][j] = 2;
			}
			else
			{
				arr[i][j] = 3;
			}
		}
	}

	int red = 0;
	int green = 0;
	int blue = 0;
	int red_green = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][j] == 1 && visited[i][j] == 0)
			{
				dfs(i, j, 1);
				red++;
			}

			if (arr[i][j] == 2 && visited[i][j] == 0)
			{
				dfs(i, j, 2);
				green++;
			}

			if (arr[i][j] == 3 && visited[i][j] == 0)
			{
				dfs(i, j, 3);
				blue++;
			}
		}
	}

	memset(visited, 0, sizeof(visited));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if ((arr[i][j] == 1 || arr[i][j] == 2) && visited[i][j] == 0)
			{
				red_green_blind(i, j);
				red_green++;
			}
		}
	}

	int normal = red + green + blue;
	int blind = red_green + blue;
	printf("%d %d", normal, blind);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ