백준 10026번: 적록색약

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

10026번: 적록색약

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

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

입력

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

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

출력

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

---

BFS를 이용해서 덩어리의 개수를 셀 건데, for i in ('R','G','B'): 반복문 안에 넣어서 R,G,B 각각의 덩어리의 수를 다 셀 수 있도록 했다.

적록색약의 경우 그림의 입력에서 R,G인 부분을 찾아 Y로 변경한 후, for i in ('Y','B'): 반복문 안에 넣어 실행시켰다.

(Y로 한 이유는..적록색약이면 어떻게보이나 검색하니까 노란색처럼 보이길래 그냥 내맘대로 Y로 함)

 

from collections import deque
n=int(input())

#그림 입력받기
field=[]
for i in range(n):
    field.append(list(map(str,input())))

#방문표시할 리스트 초기화
visited=[[0]*n for i in range(n)]

dx=[1,-1,0,0]
dy=[0,0,1,-1]
queue=deque()
def bfs(x,y,RGB):
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(4): #동서남북 탐방
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n: #그림을 벗어나면 중단
                continue
            if field[nx][ny]==RGB and visited[nx][ny]==0:옆에 방문하지 않은 같은색이 있으면 탐색
                visited[nx][ny]=1
                queue.append((nx,ny))

#RGB덩어리 찾기
RGB_count=0
for RGB in ('R','G','B'):
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0 and field[i][j]==RGB:
                bfs(i,j,RGB)
                RGB_count+=1 #구역 수 카운트

print(RGB_count)

#적록색약 RGB찾기
visited=[[0]*n for i in range(n)] #방문표시 초기화
#그림에서 R,G인 부분 Y로 변경
for i in range(n):
    for j in range(n):
        if field[i][j]=='R' or field[i][j]=='G':
            field[i][j]='Y'

#YB덩어리 찾기
YB_count=0
for YB in ('Y','B'):
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0 and field[i][j]==YB:
                bfs(i,j,YB)
                YB_count+=1 #구역 수 카운트

print(YB_count)

이차원배열~반복문 다 떡칠을해놔서 메모리초과나 시간초과뜨나 싶었는데 그냥 됐음..

 

그리고 생각해보니까 for i in ('R','G','B'): 이 반복문은 돌릴 필요가 없었음

방문한건 다 방문표시 될테니까 저거 안돌려도 알아서 카운트는 세 지는거임.....

 

아무튼 그거 빼면 좀 더 간결할듯~ 암튼 난 이해함