10026. 적록색약

문제 코드

from collections import deque

N= int(input())

graph = [[0 for col in range(N)]for row in range(N)]

for i in range(N):
    graph_row = input()
    for j in range(N):
        graph[i][j] = graph_row[j]

visited = [[0 for col in range(N)]for row in range(N)]

count = 0

color_list =["R","G","B"]
for color in range(3):
    while True:
        find = False
        for i in range(N):
            if find == True:
                break
            for j in range(N):
                if graph[i][j] == color_list[color] and visited[i][j] == 0 :
                    start = [i,j]
                    find = True
                    break

        if find == False:
            break

        que = deque()

        que.append(start)

        visited[start[0]][start[1]] = 1

        while len(que)>0:
            x,y = que.popleft()


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

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

                if 0<=next_x<N and 0<=next_y<N and visited[next_x][next_y] == 0 and graph[next_x][next_y] == color_list[color]:
                    que.append([next_x,next_y])
                    visited[next_x][next_y] = 1

        count+=1


for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

color_list =["R","B"]

two_color_count = 0
visited = [[0 for col in range(N)]for row in range(N)]
for color in range(2):
    while True:
        find = False
        for i in range(N):
            if find == True:
                break
            for j in range(N):
                if graph[i][j] == color_list[color] and visited[i][j] == 0 :
                    start = [i,j]
                    find = True
                    break

        if find == False:
            break

        que = deque()

        que.append(start)

        visited[start[0]][start[1]] = 1

        while len(que)>0:
            x,y = que.popleft()
            
            dx = [-1,1,0,0]
            dy = [0,0,-1,1]

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

                if 0<=next_x<N and 0<=next_y<N and visited[next_x][next_y] == 0 and graph[next_x][next_y] == color_list[color]:
                    que.append([next_x,next_y])
                    visited[next_x][next_y] = 1

        two_color_count+=1

print(count, two_color_count)

문제 풀이

• R,G,B 3개의 값 순서대로 가장 처음 나오는 곳을 찾는다.
• 가장 처음 나온곳을 기준으로 4방향 이동하며 같은 값을 찾는다.
• visited를 갱신하면서 가다가, 더이상 que가 없으면 count를 하나 증가시키고 다시 처음부터 그래프를 찾아서 다음 R,G,B 값을 찾는다.
• 최종 count의 개수가 구역의 개수
• 적록색약은 R을 G와 일치시켜주고 찾는다.