[백준 - Python] 10026. 적록색약 (DFS/BFS)

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

10026번: 적록색약

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
draw = [[] for _ in range(n)]
draw_rg = [[] for _ in range(n)]

for i in range(n):
    row = input()
    for r in row:
        draw[i].append(r)
        draw_rg[i].append(r)

# draw_rg = draw의 문제점 ?!

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

def dfs(x, y, draw):
    col = draw[x][y]
    draw[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if draw[nx][ny] == col:
                dfs(nx, ny, draw)

def dfs_rg(x, y, draw_rg):
    col = draw_rg[x][y]
    draw_rg[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if col == 'R' or col == 'G':
                if draw_rg[nx][ny] == 'R' or draw_rg[nx][ny] == 'G':
                    dfs_rg(nx, ny, draw_rg)
            if col == 'B':
                if draw_rg[nx][ny] == 'B':
                    dfs_rg(nx, ny, draw_rg)

cnt = 0
for i in range(n):
    for j in range(n):
        if draw[i][j] != 0:
            dfs(i, j, draw)
            cnt += 1
print(cnt)

cnt2 = 0
for i in range(n):
    for j in range(n):
        if draw_rg[i][j] != 0:
            dfs_rg(i, j, draw_rg)
            cnt2 += 1
print(cnt2)

 

dfs로 풀었고, 조건만 잘 걸어주면 쉽게 풀릴 문제라 생각하고

문제를 풀기 시작했다.

 

적록색약인 사람이 봤을 때의 구역의 개수를 구하는 dfs를 따로 만들어 주었는데,

R, G, B 정보가 저장된 draw 2차원 배열의 값들을

적록색약이 아닌 사람이 봤을 때의 구역의 개수를 구하는 과정에서

방문한 이후에 0으로 수정해주는 과정을 거쳤기 때문에

적록색약의 dfs에서는 새로운 2차원 배열을 사용해야 했다.

 

현재 코드 이전에, draw 2차원 배열을 입력 받은 이후에

단순히 대입 연산자를 활용해서

draw_rg = draw와 같은 코드를 사용했는데,

적록색약인 사람이 봤을 때의 구역의 개수가 계속 0이 나왔다.

 

2차원 배열을 보존하기 위해 복사를

draw_rg = draw와 같이 하게 되면

전체 리스트의 주소값은 다르지만, 내부의 리스트는 같은 주소를 갖기 때문에

한 리스트의 값이 변경 됨에 따라 다른 리스트의 값도 같이 변경된다.

 

이와 관련한 자세한 내용은

다른 블로그 글로 상세하게 다뤄봐야겠다.

 

여튼!

이를 피하기 위한 방법은

내가 위의 코드에서 사용한 방법처럼

저장 시에 동시에 저장을 해주는 방식도 있지만,

깊은 복사를 활용하는 방식이 있다.

 

import copy
a = [[1, 2], [3, 4]]
b = copy.deepcopy(a)
a[1].append(5)
print(a)
print(b)

 

위 코드의 출력값은

[[1, 2], [3, 4, 5]]
[[1, 2], [3, 4]] 으로

값이 독립적으로 변경되었음을 확인할 수 있다.