bj10026 적록색약

coh·2022년 5월 27일
0

백준

목록 보기
13/27

input data 어떤 자료형으로?

우선 문제를 풀기위해 input을 어떻게 받을지부터 고민을 했다.
node구조로 받아야 할까 아니면 이중 list로 받아야 할까..
node구조로 받으면 self.(up, down, left, right) 이렇게 써야할 거 같았고 또 양방향이기 때문에 self.prev.(up ~) 써야하는 변수가 엄청 많아질 것 같았다.
그래서 이중 list를 써야겠다고 생각했다.

Breadth_first_search

그 다음에는 search를 하면서 영역의 갯수를 세어야 했다.
여기서 막혀서 idea를 듣고 문제를 풀었다.. 하.. 왜 이런 기발한 방법을 생각하지 못했을까. 그냥 color가 같을 때를 탐색하니까 이미 이전에 탐색했던 노드들로 계속 가서 실패했다.. ㅠㅠ

search를 하면서 해당 인덱스를 탐색했으면 'X'표를 쳐서 다시 탐색하지 않도록 했다. 그리고 인접 node들을 탐색할 때 인접 노드가 같은 color인지를 check하면서 'X'표를 채워 나갔다. 동시에 breadth first search를 진행했다!

import copy


def check_move(graph, row, col, color):
    if row < 0 or row >= size:
        return False
    if col < 0 or col >= size:
        return False
    if graph[row][col] != color:
        return False
    if graph[row][col] == 'X':
        return False
    return True


def breadth_first_search(graph, row, col):
    # if graph[row][col] != 'X':
    #     breadth_first_search.count += 1
    color = graph[row][col]
    graph[row][col] = 'X'
    stack = [(row, col)]
    # move left, right, down, up
    move = [[0, -1], [0, 1], [1, 0], [-1, 0]]
    while len(stack):
        row, col = stack.pop()
        for m in range(4):
            next_row, next_col = row, col
            next_row += move[m][0]
            next_col += move[m][1]

            if not check_move(graph, next_row, next_col, color):
                continue
            stack.append((next_row, next_col))
            graph[next_row][next_col] = 'X'


size = int(input())
RGB_card = []
# breadth_first_search.count = 0
for i in range(size):
    RGB_card.append([])
for i in range(size):
    RGB_card[i] = list(input())

copied_RB = copy.deepcopy(RGB_card)
copied_RGB = copy.deepcopy(RGB_card)
for i in range(size):
    for j in range(size):
        # 적록색약!
        if copied_RB[i][j] == 'G':
            copied_RB[i][j] = 'R'

RB_count = 0
RGB_count = 0
for i in range(size):
    for j in range(size):
        if copied_RB[i][j] != 'X':
            RB_count += 1
            breadth_first_search(copied_RB, i, j)
        if copied_RGB[i][j] != 'X':
            RGB_count += 1
            breadth_first_search(copied_RGB, i, j)

print(RGB_count, RB_count)
profile
Written by coh

0개의 댓글