[백준 10026 / Python] 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

접근 방식

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

-> 상하좌우 리스트를 만들어서 bfs를 이용해 같은 구역을 추출한다.

-> 그림 안에서  bfs로 방문표시와 함께 같은 구역을 추출해 크게 구역을 나눈다.

 

적록색약인 경우 그림에서 R과 G를 같게 설정한뒤 bfs를 통해 구역을 나눈다.

-> 위에서 썼던 방문표시리스트를 초기화해서 bfs를 돌아 구역을 나눈다.

 

구역을 나누면서 나눈 구역을 카운트해 구역개수를 센다.

 

 

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
arr = list(input().strip() for _ in range(n))
visited = [[0]*n for _ in range(n)]
cnt_1=0 # 정상인 사람이 봤을때 구역 수
cnt_2=0 # 적록색약인 사람이 봤을때 구역 수
def bfs(a,b):
    dx = [-1,+1,0,0]
    dy = [0,0,-1,+1]
    queue = deque()
    queue.append([a,b])
    visited[a][b]=1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if not visited[nx][ny] and arr[x][y]==arr[nx][ny]: #같은 색깔일때
                visited[nx][ny]=1
                queue.append([nx, ny])

    return

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

visited = [[0]*n for _ in range(n)]


for i in range(n):
    arr[i] = arr[i].replace('R','G')


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

print(cnt_1,end=' ')
print(cnt_2)