2021. 3. 8. 03:28ㆍ알고리즘/파이썬
적록색약 [10026]
백준 - https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
깃헙 - https://github.com/shs9509/study
문제
-
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다.
-
따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
-
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
-
그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
-
또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
-
예를 들어, 그림이 아래와 같은 경우에
-
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1)
-
하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
-
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
-
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
-
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
-
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
풀이과정
-
DFS 방식을 통해서 각 섹션을 구분해서 값을 구했다.
-
처음에는 RGB를 구분하고 [RG] =0 [B] =1 로해서 0 1 로 구분해서 두번! 하려고했다.
-
하지만 비효율적이고 이문제에 한해서 풀어지는거기 때문에 함수를 만들었다.
-
2차원 배열 visited를 이용해서 방문한 지역을 체크한다.
-
섹션의 구분을 B구역 R구역 G구역 RG구역으로 나눠지기 때문에 구역을 함수인자로 받는다.
-
결과는 구역마다의 합으로 나타낸다.
-
적록색약 -> B구역 + RG구역
-
일반인 -> R구역 + B구역 + G구역
-
느낀점
-
그냥저냥 했다면 두번 돌렸을텐데 성장이없는거 같아 함수로 만들어서 해보았다.
-
RGB 구분하고 RG B를 한번더 구분을 어떻게 할까 고민했는데.
-
visited 배열을 통해 나타내니 간단해졌다.
-
-
DFS 와 재귀로도 많이 풀었던데 나도 한번 그렇게 풀어봐야겠다.
-
처음에는 함수 인자가 여러개가있어서 (ex. R,G,B,RG) 인자를 *args 이런식으로 받아야하나 생각했다.
-
그런데 엄두가 안났다. ㅎ
-
'알고리즘 > 파이썬' 카테고리의 다른 글
안전 영역 [2468] (0) | 2021.03.14 |
---|---|
암호만들기 [1759] (1) | 2021.03.12 |
일곱 난쟁이 [2309] (0) | 2021.03.08 |
블랙잭 [2798] (0) | 2021.03.08 |
색종이 [10163] (0) | 2021.02.24 |