[BOJ] 10026 : 적록색약

Question

---

Solution

• 맵 크기, 방문처리, 다음 노드(dx, dy) 선언.
• for문에서 모든 요소에 대하여 DFS 탐색을 한다, 탐색시 count 증가.
• 다음 노드로 넘어갈땐 같은 문자여야만 넘어가도록 한다.
• 적녹색인 사람의 경우 R과 G를 같은 문자로 map을 다시 재구성해준다, count, 방문처리도 초기화 시킨다.
• 적녹색이 사람에 대한 DFS 재 탐색.

---

Cord

#include <iostream>
#include <memory.h>

#define SIZE 101

using namespace std;

int n;
char current;

char map[SIZE][SIZE];
bool visited[SIZE][SIZE];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

void dfs(int _x, int _y)
{
	for (int i = 0; i < 4; i++)
	{
		int nextX = _x + dx[i];
		int nextY = _y + dy[i];

		if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n)
		{
			if (!visited[nextY][nextX] && map[_y][_x] == map[nextY][nextX])
			{
				visited[nextY][nextX] = true;
				dfs(nextX, nextY);
			}
		}
	}
}

int main()
{
	// 크기 입력 n x n
	cin >> n;

	// 맵에 그림 배치
	char temp;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> temp;
			map[i][j] = temp;
		}
	}

	// DFS 탐색
	// 적록색 아닌 사람
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j])
			{
				current = map[i][j];
				count++;
				visited[i][j] = true;
				dfs(j, i);
			}
		}
	}
	cout << count << ' ';
	
	// 적록색인 사람
	// 초기화
	count = 0;
	current = ' ';
	memset(visited, false, sizeof(visited));
	// 맵 재구성
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == 'G')
			{
				map[i][j] = 'R';
			}
		}
	}

	// DFS 탐색
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j])
			{
				count++;
				visited[i][j] = true;
				dfs(j, i);
			}
		}
	}
	cout << count;

	return 0;
}

---

Result

What’s new

배열을 손쉽게 다시 초기화 하는 법

// 둘 중 하나 아무거나 사용
#include <memory.h>
#include <string.h>

// *ptr = 세팅하고자 하는 메모리의 시작 주소
// value = 세팅하고자 하는 값 (다른 타입의 자료도 가능)
// num = 길이
memset(void *ptr,int value, size_t num);