글 읽기 - 10026(적록색약) 질문

whgkdrjs4321 4년 전 0

DFS를 연습하는 과정에서 푼 문제인데 , 시간 초과 에러가 뜨는 것도 아니고 그냥 틀렸다고만 떠서 어느 부분이 틀렸는지 궁금하여 질문을 드립니다.

참고로 코드가 조금 더럽습니다만 그건 양해해주십시오. 아직 DFS쪽은 익숙하지 않아서...

#include <iostream>
#include <cstring>
using namespace std;

char rgb[101][101];						//RGB를 저장할 배열
int visited[101][101] = { 0, };			//visited[i][j]를 방문한 경우는 1, 방문하지 않은 경우는 0을 출력
int n, cnt = 0;							//n = 개수, cnt = 적록색약이 아닌 사람의 저장할 구역의 수
int cnt2 = 0;							//cnt2 = 적록색약인 사람의 저장할 구역의 수

void dfs(int a, int b)
{
	for (int i = a;i <= n;i++)
	{
		for (int j = b;j <= n;j++)
		{
			if (visited[i][j])			//탈출조건
				return;

			visited[i][j]++;									//자기 자신도 방문한 것이므로 1증가

			if (rgb[i][j] == rgb[i][j + 1] && j < n)			//오른쪽이 같은 경우
			{
				dfs(i,j + 1);
			}

			if (rgb[i][j] == rgb[i][j - 1] && j >= 2)			//왼쪽이 같은 경우
			{
				dfs(i,j - 1);
			}

			if (rgb[i][j] == rgb[i + 1][j] && i < n)			//아래쪽이 같은 경우
			{
				dfs(i + 1,j);
			}

			return;
		}

	}
}

int main()
{
	cin >> n;

	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			cin >> rgb[i][j];
	
	
	for (int i = 1;i <= n;i++)					//적록색약이 아닌 사람이 본 경우 구역의 수 구하기
	{
		for (int j = 1;j <= n;j++)
		{
			if (!visited[i][j])
			{
				dfs(i, j);
				cnt++;
			}
		}
		
	}

	memset(visited, 0, sizeof(visited));		//visited를 0으로 초기화

	for (int i = 1;i <= n;i++)					//R과 G를 같게 바꾸기 -> 적록색약을 위한 과정
	{
		for (int j = 1;j <= n;j++)
		{
			if (rgb[i][j]=='G')
			{
				rgb[i][j] = 'R';
			}
		}

	}

	for (int i = 1;i <= n;i++)					//적록색약인 사람이 본 구역의 수 구하기
	{
		for (int j = 1;j <= n;j++)
		{
			if (!visited[i][j])
			{
				dfs(i, j);
				cnt2++;
			}
		}

	}

	cout << cnt <<' ' <<cnt2 << endl;

	return 0;
}

exponential_e 4년 전 2

아래의 예제에서 잘못된 출력을 합니다.

색약이 아닌사람의 경우 3 색약인 경우 2

dfs 부분에서 위쪽 부분은 탐색을 안하시는데 아마 그 문제가 아닌가 싶습니다.

5
BBBBB
BBGBG
BGGGG
BBRRR
RRRRR

exponential_e 4년 전 1

아 참고로 작성자님 코드로 돌렸을땐

4 3을 출력합니다.

whgkdrjs4321 4년 전 1

정말로 감사합니다. exponential_e님 말씀대로 위쪽 부분 탐색을 추가하였더니 정답처리가 되었습니다.

rgb[1][1]부터 시작해서 위쪽 부분은 탐색을 안해도 될거라고 생각했는데 필요했네요. 정말로 감사드립니다.

exponential_e 4년 전 1

일부러 없어도될거라고 생각하고 빼신거같아서 필요할만한 케이스를 만들어봤습니다.

정답처리 받으셨다니 다행입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10026(적록색약) 질문

whgkdrjs4321 4년 전 0

exponential_e 4년 전 2

exponential_e 4년 전 1

whgkdrjs4321 4년 전 1

exponential_e 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말