문제

10026. 적록색약

• $N$x$N$ 크기의 그리드에서 R(빨강), G(초록), B(파랑) 중 하나로 색칠된 그림이 주어진다.

• 같은 색으로 상하좌우 인접한 칸들은 같은 구역으로 본다.

  # 예제 입력
  5
  RRRBB
  GGBBB
  BBBRR
  BBRRR
  RRRRR
  
  # 예제 출력
  4 3
  

  • 적록색약이 아닌 사람은 R, G, B를 각각 구분해서 구역을 센다.
    • R 2개, G 1개, B 1개 → 총 4개
  • 적록색약(빨간색과 초록색의 차이를 거의 느끼지 못하는 사람)인 사람은 R과 G를 같은 색으로 간주하여 구역을 센다.
    • R과 G를 같은 색으로 간주 (R=G) → RG 2개, B 1개 → 총 3개

• 두 경우의 구역 개수를 구한다.

힌트

문제 유형 / 시간 복잡도

아이디어

시간 복잡도

정답

1. $N$을 입력받고 $N$x$N$ 크기의 그리드를 저장한다.
2. BFS/DFS를 이용하여 같은 색의 영역을 찾는다.
   • 적록색약이 아닌 경우와 적록색약인 경우를 각각 계산해야 한다.
   • 모든 칸을 훑어보면서 아직 방문하지 않은 색이 있다면, 그 칸을 시작점으로 탐색을 시작한다.
   • 탐색하면서 상하좌우로 같은 색인 곳을 찾아가고, 방문 표시를 남긴다. 이게 하나의 구역이 된다.
3. 적록색약이 아닌 사람 기준으로 구역 탐색을 진행한다.
4. 적록색약 탐색을 위해 그리드를 변경한다.
5. 적록색약 기준으로 구역 탐색을 진행한다.