적록색약
title: “10026 - 적록색약”
date: “2019-02-18”
category: “algorithm”
문제요약
- 입력으로는 지역의 크기와 지역의 색 정보가 R, G, B로 주어진다.
- 적록색약이 있는 사람은 초록색과 빨간색을 구분하지 못한다고 한다.
- 인접한 칸중 같은 색을 갖는 칸의 집합을 1개의 구역으로 본다.
- 같은 지역에 대해 적록색약이 없는 사람과 적록색약이 있는 사람이 몇개의 구역으로 보는지 출력하여라
접근법
이 문제는 단지번호붙이기(2667)과 거의 같은 문제라고 생각하면 된다. 처음에 주어진 지역 정보를 같고 적록색약이 없는 사람은 몇개의 구역으로 보는지 파악하기 위해 모든 칸에 대해 BFS를 수행하고, 적록색약이 있는 사람의 경우를 구하기 위해 G를 전부 R로 바꾸고 다시 한번 BFS를 수행한다.
예제 입력을 통해서 좀더 자세히 살펴보자.
| R | R | R | B | B |
|---|---|---|---|---|
| G | G | B | B | B |
| B | B | B | R | R |
| B | B | R | R | R |
| R | R | R | R | R |
위와 같은 입력이 주어졌을 때 (0, 0) ~ (4, 4)까지 모든 칸에 대해 BFS를 수행하며, 구역을 찾는다. (0, 0)은 어떠한 구역에도 속해있지 않기 때문에 (0, 0)에서 구역을 찾기 위한 BFS를 수행한다. BFS를 통해 (0, 0), (0, 1), (0, 2)가 같은 구역이라는 것을 파악할 수 있다. (0, 1)과 (0, 2)는 이미 찾은 (0, 0), (0, 1), (0, 2) 구역내에 포함되기 때문에 BFS를 수행하지 않는다. (1, 0)은 지금까지 찾은 구역내에 포함되지 않기 때문에 (1, 0)에서 BFS를 수행하여, (1, 0), (1, 1)이라는 구역을 찾는다. 이와 같은 과정을 반복하며 적록색약이 없는 사람은 입력으로 주어진 지역을 몇개의 구역으로 보는지 파악한다. 다음으로 적록색약이 있는 사람의 경우를 계산하기 위해 지역내 G를 R로 바꿔 준다.
| R | R | R | B | B |
|---|---|---|---|---|
| R | R | B | B | B |
| B | B | B | R | R |
| B | B | R | R | R |
| R | R | R | R | R |
G를 R로 바꾸고 난뒤 다시한번 위와 같은 과정을 반복함으로써 적록색약을 가진 사람은 해당 지역을 몇개의 구역으로 보는지 계산할 수 있다. 이렇게 계산된 값을 출력하면 문제를 통과할 수 있다.
Source Code
- 아직 주석이 달려있지 않습니다.
- pseudocode 보다는 python 코드를 올릴 예정입니다.
- Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)
댓글남기기