[백준 / #10026 / C++] 적록색약

이 문제는 저번에 풀었던 단지번호붙이기 문제와 흡사하다.

 

어떻게 보면 더 쉬운 문제인데 필자는 중간에 메모리 문제로 인해 조금 헤매어 오래걸렸다 ㅠㅠ

 

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

10026번: 적록색약

 

 

단지번호붙이기 문제도 살펴보고 싶다면 아래의 링크를 통해 설명을 한 번 보고 오는 것을 추천한다.

 

https://seoul-doggy.tistory.com/5

[백준 / #2667 / C++] 단지번호붙이기

 

 

문제해석:

 

 

이 문제는 우선 보자마자 단지번호붙이기 문제가 생각났다. 문제에서 주어진 자료형의 최대 크기는 100 x 100 의 크기로

 

10,000, 그렇게 크지 않은 숫자이다. 따라서 모든 색을 탐색하고도 10,000의 시간 밖에 걸리지 않기 때문에 적록색약인 사

 

람이 봤을 때와 아닌 사람이 봤을 때 모두 각각의 연산을 실행해도 시간 안에 충분히 나올 것이다. 또한 문제에서 주어진 조

 

건은 적록색약인 사람은 R과 G의 차이를 느끼지 못하는 것이었으므로 적록색약의 경우에는 R과 G를 같은 색으로 취급해

 

주고 탐색하면 되는 문제이다. 이러한 과정에서 너비우선탐색(BFS)과 깊이우선탐색(DFS)이 떠올랐다. 필자는 너비우선탐

 

색으로 풀기는 했지만 깊이우선탐색으로도 충분히 풀릴 문제이니 두 풀이 모두 가능할 것이다. 하지만 이 포스팅에서는 너

 

비우선탐색(BFS)에 대해서만 다루겠다.

 

 

알고리즘 해설 및 코드:

 

 

코드를 살펴보자.

 

 위에 문제 해석에서 언급했듯이 적록색약은 초록과 빨강을 구분하기 힘들기 때문에 같은 색으로 만들어줘야한다. 따라서 

 

그림 배열을 3차원으로 선언해 첫번째 면에는 적록색약이 아닌 사람이 볼 그림을, 두번째 면에는 적록색약인 사람이 볼 그

 

림을 저장했다. 이렇게 배열이 두개 필요한 이유는 BFS탐색을 하면 지나온 경로들을 지우게 되는데 적록색약인 사람과 적

 

록색약이 아닌 사람의 배열이 한 배열에 겹치면 복구를 다시 해주는 등 연산이 복잡해지기 때문에 두개로 만들어주었다. 사

 

실 처음부터 배열은 하나로 두고 bool타입의 visit배열을 하나 선언해줘도 된다. 하지만 편의상 3차원 배열로 설정하였다.

 

 

 이렇게 선언이 끝나면 배열에 입력 받을 때 적록색약인 사람은 만약 빨강인 R 입력이 들어온다면 G로 바꿔 저장하도록 하

 

였다. 그렇게되면 적록색약이 보는 그림과 아닌 사람이 보는 그림의 배열이 완성되었다. 이렇게 완성된 배열을 모두 하나씩

 

돌면서 BFS탐색을 실행해주면 된다. BFS로 인접한 같은 색들을 지워주는 연산을 실행한다. 이렇게 지우고 나면 다음 칸으

 

로 이동해 다음 칸이 이미 지워져있는지 혹은 아직 색이 남아있는지를 판단해 또 다시 BFS 연산을 실행해준다. 이렇게 하

 

면 BFS 연산이 실행될 때마다 그 곳은 아직 인접한 색을 만나지 않아 지워지지 않았다는 것이고 이는 곧 영역이 아직 살아

 

있음을 의미하기 때문에 영역의 크기를 +1 해주면 된다. 적록색약도 마찬가지의 연산을 실행해주면된다.

 

 

 이 알고리즘은 한마디로 BFS를 같은 영역을 지워주는 연산으로 사용한 것이다. 이 점을 참고하면 좋을 것이다.

 

 

 

 

이렇게 문제를 마무리하면서, 이 문제는 단지번호붙이기 문제와 너무 유사한 탓에 설명할 것이 그렇게 많지 않다. 공부하기

 

위함이라면 단지번호붙이기 문제를 보고오길 강력추천해드린다.