🖋️ 문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
🤔 접근
그냥 DFS 두 번 돌려도 시간초과 안 날 것 같다고 생각해서 바로 구현
💻 내 코드
import copy
import sys
sys.setrecursionlimit(10**7)
def dfs(tmp, x, y, color):
tmp[x][y] = 0 # 방문처리
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if (0<=nx<n) and (0<=ny<n):
if tmp[nx][ny] == color:
dfs(tmp, nx, ny, color)
def dfs2(table, x, y, color):
table[x][y] = 0 # 방문처리
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if (0<=nx<n) and (0<=ny<n):
if table[nx][ny] == 'R':
table[nx][ny] = 'G'
if table[nx][ny] == color:
dfs2(table, nx, ny, color)
n = int(input())
table = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
tmp = copy.deepcopy(table) # 깊은 복사
count = 0
count2 = 0
for i in range(n):
for j in range(n):
color = tmp[i][j]
if tmp[i][j]:
dfs(tmp, i, j, color)
count += 1
if table[i][j]:
if color == 'R':
color = 'G'
dfs2(table, i, j, color)
count2 += 1
print(count, count2)👍 제출
하.. 깊이 제한 늘려주는 걸 또 깜박해서 첫 시도는 RecursionError 가 났다. 이제 정말 실수 안 해야지,,,
☑️ 정리
얕은 복사와 깊은 복사
- 얕은 복사
arr1 = [1, 2, 3]
arr2 = arr1실제로 객체 전체를 복사한 것이 아닌 메모리주소만 복사한 것! arr1이랑 arr2랑 같은 메모리를 가리키고 있음. 그래서 arr1에 요소를 추가하거나 바꾸면 arr2도 똑같이 적용됨.
import copy
arr1 = [1, 2, [1, 2]]
arr2 = arr1[:]
# 또는
arr2 = arr1.copy()
# 또는
arr2 = copy.copy(arr1)arr1과 arr2는 참조하는 메모리 주소가 다르지만, 깊은 복사는 아니다. 리스트의 내부 리스트는 arr1과 arr2가 같은 메모리 주소를 사용하고 있습니다.
- 깊은 복사
import copy
arr1 = [1, 2, [1, 2]]
arr2 = copy.deepcopy(arr1)깊은 복사는 각각의 리스트와 내부리스트 모두 독립적인 메모리 주소를 참조합니다. 복사 이후로는 두 리스트가 서로 전혀 영향을 주고받지 않습니다.
RecursionError
RecursionError 가 가장 많이 발생하는 이유는 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.
발생하는 이유에 대해 자세히 알아보겠습니다. 구체적으로 알기 위해서 메모리 구조를 공부해보았습니다.
프로그램이 실행되면 운영체제는 프로그램에 적당한 메모리 공간을 할당해줍니다. 메모리의 구성은 크게 4가지로 구분할 수 있습니다.
1. 코드 영역
2. 데이터 영역
3. 스택 영역
4. 힙 영역
그 중에서 저희가 살펴보아야 하는 곳이 스택 영역입니다. 스택 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 공간입니다. 함수가 호출되면 생성되고 함수 실행이 완료되면 사라집니다. 재귀함수가 실행되면 함수가 종료되지 않은 채로 계속 함수가 실행되기 때문에 이 경우 스택 공간이 초과되는 스택 오버플로우가 발생할 수 있습니다. 그래서 python3 기준 최대 재귀 깊이가 1000으로 제한되어 있다. 따라서 재귀함수를 이용하여 문제를 풀 때에는 최대 재귀 깊이를 늘려주어야 RecursionError 를 마주하지 않을 수 있다.
