문제 원본 :
10026번: 적록색약
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은
www.acmicpc.net
출처 : USACO(미국정보올림피아드) 2013-2014 Season USACO March 2014 Contest Bronze 3번
풀이법은 다음과 같습니다.
먼저 적당한 배열을 선언하여 그림을 입력 받습니다.
입력되는 그림의 크기가 여유롭기 때문에 본문에서는 정상그림과 색약그림을 따로 저장했습니다. (본문에서 ab, disab)
Flood Fill 알고리즘을 사용하여 정상그림과 색약그림의 각 인접한 칸들을 지워가며 영역의 개수를 확인합니다.
그림을 모두 확인한 후 저장된 정상영역과 색약영역을 출력하면 됩니다.
Flood Fill 알고리즘을 사용할 때에는 선언한 배열을 초과하는 곳을 건드리지 않도록 설정해주는 것이 중요합니다.
'OJ 문제풀이 > BOJ' 카테고리의 다른 글
| BOJ #11053 가장 긴 증가하는 부분 수열 (0) | 2019.10.07 |
|---|---|
| BOJ #1976 여행 가자 (0) | 2019.09.24 |
| BOJ #1932 정수 삼각형 (0) | 2019.09.23 |
| BOJ #6198 옥상 정원 꾸미기 (0) | 2019.09.22 |
댓글