10026

날짜 : 2022. 12. 03

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque
import copy

n = int(sys.stdin.readline())
area = list()
v1 = [[False] * n for i in range(n)]
v2 = [[False] * n for i in range(n)]  # 적녹색약

for _ in range(n):
    t = sys.stdin.readline().rstrip()
    temp = []
    for i in t: temp.append(i)
    area.append(temp)

area2 = copy.deepcopy(area)
for i in range(n):
    for j in range(n):
        if area2[i][j] == "G":
            area2[i][j] = "R"  # 적, 녹 색깔 통일


def BFS(idx, a, b, color):
    q = deque()
    q.append([a, b])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while q:
        temp = q.popleft()
        for i in range(4):
            x = temp[0] + dx[i]
            y = temp[1] + dy[i]
            if x in range(n) and y in range(n):  # 범위 안에 있는 경우
                if idx == 1:
                    if not v1[x][y] and area[x][y] == color:  # 동일한 색깔이고 방문하지 않은 경우
                        v1[x][y] = True  # 방문처리
                        q.append([x, y])  # 큐에 추가
                elif idx == 2:
                    if not v2[x][y] and area2[x][y] == color:  # 동일한 색깔이고 방문하지 않은 경우
                        v2[x][y] = True  # 방문처리
                        q.append([x, y])  # 큐에 추가
    return


cnt1, cnt2 = 0, 0
for i in range(n):
    for j in range(n):
        if not v1[i][j]:  # 방문 x
            cnt1 += 1
            BFS(1, i, j, area[i][j])
            #print("%d %d, %s"%(i, j, area[i][j]))
        if not v2[i][j]:
            cnt2 += 1
            BFS(2, i, j, area2[i][j])
            #print("%d %d, %s" % (i, j, area[i][j]))

print(cnt1, cnt2)

 

 

풀이

- 보통의 BFS / DFS 방식으로 풀 수 있는 문제였고 다만 적녹색약 특성을 넣어서 빨강과 초록값을 통일시켜야 한다는게 이 문제의 골자였다.

- 문제를 풀기위해 깊은복사를 활용했고 복제 후 R값과 G값을 통일하였다.

- BFS에서는 argument 중에 idx와 color를 추가하여 적녹색약 여부와 색깔의 동일 여부를 분기하였다.

 

 

알게된 점

- 

 

 

참고 사이트

- 깊은복사와 얕은복사 : https://wikidocs.net/16038

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)