[Algorithm] BAEKJOON 10026번. 적록색약 (python)

[ 백준 10026번. 적록색약 ]

• 문제명 : 적록색약
• 사용 언어 : python3
• 알고리즘 : BFS(너비 우선 탐색)

---

 

  문제 

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

 

 

 

 

  알고리즘 및 코드

: 적록색약이 아닌 사람의 경우를 먼저 체크하고,

  적록색약인 사람은 'R'을 'G'로 바꿔주고 G/B인 경우를 체크하여 구현하였다. 

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x, y):
  queue = deque()
  queue.append((x, y))
  visited[x][y] = 1

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      # 범위 안에 있고, 같은 색상이고, 방문하지 않았는지 조건 확인.
      if 0 <= nx < N and 0 <= ny < N and map[nx][ny] == map[x][y] and not visited[nx][ny]:
        visited[nx][ny] = 1
        queue.append((nx,ny))


N = int(input())
map = [list(input().rstrip()) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
cnt1, cnt2 = 0, 0

# 적록색약이 아닌 사람
for i in range(N):
  for j in range(N):
    if not visited[i][j]:
      bfs(i,j)
      cnt1 += 1

# 적록색약인 사람, R->G
for i in range(N):
  for j in range(N):
    if map[i][j] == 'R':
      map[i][j] = 'G'
    
visited = [[0] * N for _ in range(N)]

for i in range(N):
  for j in range(N):
    if not visited[i][j]:
      bfs(i,j)
      cnt2 += 1


# 출력(적록색약X, 적록색약O)
print(cnt1," ", cnt2)

 

  결과

# 수정 전
cnt1 ,cnt2 = 0

# 수정 후
cnt1, cnt2 = 0, 0

런타임 에러 나다가 맞췄다.. 여기를 바로 찾지 못하고 괜한 다른 곳에서 찾다가 시간을 날렸다. 

다음부터는 이러한 세세한 곳에서도 실수가 없도록 자세히 봐야겠다 !!! ( , , , )