자율주행 자동차를 구현하는 데에 있어서 이미지 프로세싱은 아주 중요한 요소이다. 카메라를 통해 들어온 차량 전후의 모습을 파악해 차량 근처에 있는 장애물들을 빠른 속도로 파악하고, 이를 다른 센서로부터 들어온 데이터와 함께 분석해 차량에게 올바른 명령을 내려야 하기 때문이다. 이 문제에서는 간단한 이미지 프로세싱을 하고자 한다.
H×W 크기의 2차원 비트맵 이미지가 있다. 이 이미지는 H×W개의 픽셀들로 구성되어 있으며, 위에서부터 i (1≤i≤H)번째에 있고 왼쪽에서부터 j (1≤j≤W)번째에 있는 픽셀은 (i,j)로 표기할 수 있다. 각 픽셀에는 색상이 붙어 있으며, 이 색상은 1 이상 109이하의 정수로 표기할 수 있다. 픽셀 (i,j)의 색을 Ci,j라고 하자.
이 이미지에 아래와 같은 연산을 Q번 수행할 것이다: (i,j,c): 픽셀 (i,j)를 고른다. 이 픽셀과 색깔이 같으면서 가로세로로 연결되어 있는 모든 픽셀들을 선택한 뒤, 그 픽셀들의 색을 모두 c로 바꾼다.
예를 들어 아래와 같은 이미지가 있다고 하자.
이 상황에서 (3,5,3) 연산을 수행해 보자. (3,5) 픽셀은 아래와 같다.
이 픽셀의 색은 4이므로, 색이 4이면서 (3,5)와 가로세로로 연결되어 있는 픽셀들을 선택하면 아래와 같다.
이 픽셀들의 색을 모두 3으로 바꾸면 된다.
다음 연산을 수행한다면 위와 같이 이미지가 변경된 상태에서 반복적으로 수행할 것이다. 모든 연산을 수행한 뒤의 이미지를 출력하는 프로그램을 작성하라.
제약조건
1≤H≤128
1≤W≤128
모든 i, j (1≤i≤H, 1≤j≤W) 에 대해: 1≤Ci,j≤109
1≤Q≤500
각 연산 (i,j,c)에 대해: 1≤i≤H, 1≤j≤W, 1≤c≤109
주어지는 모든 수는 정수이다.
부분문제
(10점) H=1
(90점) 추가 제약 조건 없음
입력형식
첫 번째 줄에 두 정수 H와 W가 공백 하나를 사이로 두고 주어진다. 다음 H개의 줄에는 각 픽셀의 색상이 주어진다. 이 중 i (1≤i≤H)번째 줄의 j (1≤j≤W)번째 정수는 Ci,j이다. 그 다음 줄에는 Q가 주어진다. 다음 Q개의 줄에는 연산들이 순서대로 주어진다. 각 줄에는 세 개의 정수 i, j, c가 공백 하나를 사이로 두고 주어진다.
출력형식
모든 연산을 완료한 후, 최종 이미지를 H개의 줄에 W개의 정수를 공백 하나씩을 사이로 두고 출력한다.
입력예제1
1 9 1 1 2 2 2 1 1 2 2 2 1 5 1 1 5 2
출력예제1
2 2 2 2 2 2 2 2 2
2차원 비트맵 이미지가 주어지고 입력으로 특정 위치와 색깔 번호가 들어옴
'''
재귀조건 해결하기
'''
import sys # ★★★
sys.setrecursionlimit(10**5) # ★★★
def color(x,y,c):
oldc = image[x][y]
image[x][y] = c
if image[x-1][y] == oldc:
color(x-1,y,c)
if image[x+1][y] == oldc:
color(x+1,y,c)
if image[x][y-1] == oldc:
color(x,y-1,c)
if image[x][y+1] == oldc:
color(x,y+1,c)
return
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))
# print(image) 1차 디버깅
q = int(input())
for i in range(q):
x,y,c = map(int, input().split())
if image[x][y] != c: # ★★★
color(x,y,c) # ★★★
# print(image) 2차 디버깅
for i in range(1, h+1):
for j in range(1,w):
print(image[i][j], end=' ')
print(image[i][w])
'''
파이썬에서 재귀는 1000 정도로 제약이 있는데
문제에서 2^7 * 2^7 상태라 2^14은 1024인 2^10보다 크므로 아무튼 0점
'''
import sys #파이썬이 제한한 재귀조건 풀기 = recursion해제하기
sys.setrecursionlimit(10**5) #16000번 재귀하는 것을 10만 정도로 재귀 풀어줌. 10의 5승
#컬러함수
# old color가 new color와 다르다는 것을 가정
# 혹시 같게되면 무한루프가 돌게 됨
# 그러나 제약 조건에는 old와 new가 다르다는 조건이 없음
# 그래서 그 처리를 해야 오류가 안뜸. 그건 다음 번 코드에 추가
def color(x,y,c):
#image[x][y] = c 여기서 이미 이미지컬러를 바꿨으니
#oldc라는 변수를 만들어서 image x, y를 저장
oldc = image[x][y]
#이미지 xy를 color로 바꾸는 것이 목적
image[x][y] = c
#이미지와 동일한 color도 바꿔줘
if image[x-1][y] == oldc: #x-1은 아래 가짜 index[0]으로 해결
color(x-1,y,c) #재귀적으로 다시 (x-1,y,c)
#if x < h and image[x+1][y] == oldc:
if image[x+1][y] == oldc:
color(x+1,y,c)
if image[x][y-1] == oldc: #x-1은 아래 가짜 index[0]으로 해결
color(x,y-1,c)
if image[x][y+1] == oldc:
color(x,y+1,c)
return
#비트맵의 height, weight
h, w = map(int, input().split())
#비트맵에 색상이 적혀있는데 그것을 image배열에 다 받는다
image = [[0]*(w+2)] #첫번째 row 생성되고 0인 index가 아니라 1인 index를 사용하도록 준비.
#픽셀의 색상, 줄이 h개가 들어옴
for i in range(h):
#temp라는 배열에 받아서 append
#문자열이라 split을 하고 다시 integer로 변환
#map은 list가 아니므로 list로 바꿔줘야 temp에 들어가짐. temp는 값들이 적힌 list
temp = list(map(int, input().split()))
image.append([0]+temp+[0]) #이미지 번호가 1번부터 시작하므로 앞에 [0]을 추가
image.append([0]*(w+2)) #네모 밖을 둘러싸는 테두리를 만든 것
# print(image) 1차 디버깅
#q개의 줄에 q를 받고
q = int(input())
#q개 줄에 연산들이 순서대로 주어진다.
for i in range(q):
x,y,c = map(int, input().split())
#처음에 부를 때 image xy의 컬러가 c라는 뉴컬러와 다를때만 recursion
if image[x][y] != c: #처음만 체크 잘하면 됨, 새로운 컬러가 이전 것과 같은지 여부 체크
color(x,y,c) #컬러함수를 만들어서 업데이트. 상단으로 고고
# print(image) 2차 디버깅
for i in range(1, h+1): #0인 index를 안 써서 h+1이라 써야함
for j in range(1,w):
print(image[i][j], end=' ') #엔터대신에 공백넣어라
print(image[i][w]) #맨 마지막은 엔터
