[Softeer] 21년 재직자 대회 예선 - 이미지 프로세싱

문제

<배경>

자율주행 자동차를 구현하는 데에 있어서 이미지 프로세싱은 아주 중요한 요소이다. 카메라를 통해 들어온 차량 전후의 모습을 파악해 차량 근처에 있는 장애물들을 빠른 속도로 파악하고, 이를 다른 센서로부터 들어온 데이터와 함께 분석해 차량에게 올바른 명령을 내려야 하기 때문이다. 이 문제에서는 간단한 이미지 프로세싱을 하고자 한다.

 

 $H \times W$크기의 2차원 비트맵 이미지가 있다. 이 이미지는 $H\cdot W$개의 픽셀들로 구성되어 있으며, 위에서부터  $i$번째에 있고 왼쪽에서부터  $j$번째에 있는 픽셀은 $(i,j)$로 표기할 수 있다. 각 픽셀에는 색상이 붙어 있으며, 이 색상은  $1$이상  $10^9$이하의 정수로 표기할 수 있다. 픽셀 $(i,j)$의 $C_{i,j}$색을 라고 하자.

이 이미지에 아래와 같은 연산을 $Q$번 수행할 것이다:

• $(i,j,c)$: 픽셀 $(i,j)$를 고른다. 이 픽셀과 색깔이 같으면서 가로세로로 연결되어 있는 모든 픽셀들을 선택한 뒤, 그 픽셀들의 색을 모두 $c$로 바꾼다.

예를 들어 $(3,5,3)$의 연산을 하면 왼쪽에서 오른쪽 그림으로 바뀐다.

 

<입력>

<출력>

---

풀이

먼저 입력 형식에 맞게 처리를 해야한다.

여기서 사용된 하나의 아이디어는 나중에 이미지의 상하좌우 끝에서 계산을 편하게 하기 위해 자체 이미지 바깥쪽에 0으로 테두리를 만들어 주는 것이다.

이제 연산들을 수행한다.

연산을 수행할 함수로 color()라는 함수를 만들어줬다.

이때 바꾸려는 색이 이미 자신의 색과 같은 경우는 제외해줬다.

h,w = map(int,input().split())
image = [[0]*(w+2)]
for i in range(h):
    temp = list(map(int,input().split()))
    image.append([0]+temp+[0])
image.append([0]*(w+2))

q = int(input())
for i in range(q):
    x,y,c = map(int,input().split())
    if image[x][y] != c:
        color(x,y,c)

 

 

color함수는 자신의 상하좌우에 자신과 같은 색이 있는 타일의 색을 새로운 색 c로 바꾸는 재귀함수이다.

여기서 상하좌우의 경계에 있는 값들을 따로 경우를 나누지 않아도 되는 이유는 위에서 테두리에 0을 한줄씩 추가했었기 때문이다.

def color(x,y,c):
    oldc = image[x][y]
    image[x][y] = c
    if image[x-1][y] == oldc:
        color(x-1,y,oldc)
    if image[x+1][y] == oldc:
        color(x+1,y,oldc)
    if image[x][y-1] == oldc:
        color(x,y-1,oldc)
    if image[x][y+1] == oldc:
        color(x,y+1,oldc)
    return

그런데 문제 조건에서 이미지의 크기가 128*128까지 가능하기 때문에 재귀도 128*128만큼 돌 수 있다.

파이썬은 기본적으로 재귀를 1000번 정도로 제한해 놓았기 때문에 재귀제한을 풀어줘야한다.

따라서 아래 코드를 추가했다.

import sys
sys.setrecursionlimit(10**6)

 

 

위의 코드들을 모두 합치면 문제를 풀 수 있다.