1 분 소요

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다.

따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.

그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.

또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다.

(색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다.)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다.

(빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.


입력 조건

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.


출력 조건

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.


첫 번째 시도 .

from collections import deque

n = int(input())

#그림 만들기.
pic = []
for i in range(n):
  pic.append(list(input()))



#이동량(변화량) 만들기
#상/하/좌/우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

#BFS 탐색 알고리즘 만들기.
def dfs(x,y,color):
  q = deque([(x,y)])
  visited[x][y] =True
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or ny < 0 or nx > n-1 or ny > n-1:
        continue 

      if pic[nx][ny] in color and not visited[nx][ny]:
        visited[nx][ny] = True
        q.append((nx,ny))

#BFS를 호출하여 색상 구분
result = []
for k in range(2):
  visited = [[False]*n for _ in range(n)]
  count = 0

  for i in range(n):
    for j in range(n):
      color = []
      color.append(pic[i][j])
      if k == 1 and color == ['G']:
        color.append('R')
      if k == 1 and color == ['R']:
        color.append('G')
      
      if not visited[i][j]:
        dfs(i,j,color)
        count+=1
  result.append(count)
print(*result,sep=' ')

»intput

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

»output

4 3

success

image-20220317231644652


🌝 Thinking

[아이디어]

  1. 모든 좌표를 순회하며 BFS를 한다. 이때 BFS가 동작 될 때마다 count+=1을한다.

  2. 방문 대상은 방문하지 않은 곳과 색상 리스트안에 있는 색의 경우이다


    key point. 탐색 _시작 지점의 색_을 리스트에 담아서 처리한다.

    ​ 따라서, 색약 모드 일 때는 시작 지점의 색이 ‘R’ 또는 ‘G’라면

    ​ 리스트에는 [‘R’,’G] 두 색상이 모두 담겨 있게끔 한다.



💡 깨달은 점.

  1. BFS 탐색알고리즘을 사용할 때 특정 조건에서 탐색을 원할 때(문자열 조건)일 때는 리스트와 in 함수를 이용하면 쉽게 구현이 가능했다!

댓글남기기

참고