[Baekjoon] 10026_적록색약

Gold V

문제(출처: https://www.acmicpc.net/problem/10026)

---

<적록색약>

문제 

 

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력 

 

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

 

 

문제 풀이

   - my solution

import sys

def RGB(graph, i,j, visited, flag): # 그림, x, y, 방문, 적록색약 구분
    dx=[-1,0,0,1] # 상,좌,우,하
    dy=[0,-1,1,0]

    queue=[[i,j]]
    visited[i][j]=1
    while queue:
        a,b=queue.pop(0)
        for i in range(4):
            x=a+dx[i]
            y=b+dy[i]
            if x>=0 and x<len(graph) and y>=0 and y<len(graph): #범위에 속하면
                if flag==0: # 적록색약 x
                    if visited[x][y]==0 and graph[a][b]==graph[x][y] :
                        queue.append([x,y])
                        visited[x][y] = 1
                else: # 적록색약
                    if visited[x][y]==0:
                        if graph[a][b]=='R' or graph[a][b]=='G': # R,G 구분 x
                            if graph[x][y]=='R' or graph[x][y]=='G':
                                queue.append([x,y])
                                visited[x][y] = 1
                        else: # B
                            if graph[a][b]==graph[x][y] :
                                queue.append([x,y])
                                visited[x][y] = 1


if __name__=='__main__':
    n=int(input())

    graph=[]
    visited=[[0] *n for i in range(n)]
    visited_RG_B=[[0] *n for i in range(n)] # 적록색약

    for i in range(n): #input
        graph.append(list(sys.stdin.readline().strip()))

    rgb_cnt=0
    rg_b_cnt=0 # 적록색약
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0: # 방문 x
                rgb_cnt+=1
                RGB(graph, i,j, visited,0)
            if visited_RG_B[i][j]==0: # 적록색약_ 방문 x
                rg_b_cnt+=1
                RGB(graph, i, j, visited_RG_B,1)

    print(rgb_cnt, rg_b_cnt)

 

• RGB (그림, x, y, 방문 여부 list, 적록색약 구분)
  : dx, dy = 상좌우하 탐색
  : queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 상좌우하를 확인하여 그림 범위에 속하면 -> 적록색약인지 아닌지 flag 통해 확인
  : 적록색약이 아니면 = 아직 방문하지 않았으며 현재 위치와 이동한 위치가 같은 값인지 확인 후 queue에 넣고 방문한 것으로 표기
  : 적록색약이면 = 아직 방문하지 않았다면 = 현재 값이 R, G이며 이동한 위치의 값이 R, G라면 queue에 넣고 방문한 것으로 표기 but B라면 B인지 확인 후 queue에 넣고 방문한 것으로 확인
• main
  : graph = 그림
  : visited = 적록색약이 아닌 사람의 방문 list
   visited_RG_B = 적록색약인 사람의 방문 list
  : input = 그림 입력
  : rgb_cnt, rg_b_cnt = 적록색약이 아닌 구역 개수, 적록색약 구역 개수
  : 전체 순환하며 적록색약이 아닌 사람과 적록색약인 사람이 아직 방문하지 않았다면 RGB 함수 호출하여 구역 구함

 

❓ 처음에 시간 초과가 발생한 이유는 무엇인가?

RGB 함수 안에서 visited를 처리하는 과정에서 발생한 것이었다. 내가 처음 작성한 코드는 queue에서 pop 한 후 visited를 1로 바꿔주는 것이었다. 이렇게 될 경우 만약 queue에 [[1,0], [1,1]] 이 있다면 [1,1]은 아직 visited 값이 0이기 때문에 queue에 또 추가될 수 있다. 이 과정에서 똑같은 값이 여러 번 진행되면서 시간 초과가 발생하는 것이었다. 그러므로 queue에 넣으면서 visited를 1로 바꿔주도록 했더니 통과할 수 있었다.

 

---

생각🤔

 

처음 코드를 제출하고 시간 초과가 발생하여 안 믿겨 다시 제출해봤다.. 😥

한 줄 차이로 시간 초과가 갈리다니 그래도 이해 완료 -!

 

이런 거 알려주는 사람은 진짜 대단한 것 같다. 나도 더 분발해야겠다 🤔

 

---