[Softeer]이미지 프로세싱 파이썬 풀이
Softeer 이미지 프로세싱¶
문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=627
문제가 복잡하므로 우선 input과 우리가 구해야하는 output에 대해 생각을 해보자.
'''
inputs:
- H, W:
H: img 행의 갯수, W: img 열의 갯수
- colors: 각 img pixel에 해당하는 color의 번호
- Q: color를 바꿀 연산의 횟수
- i, j, c:
i: 행 번호, j: 열 번호, c: color 번호
output:
- img: 연산의 결과 바뀐 img
'''
입력의 경우 i, j, c가 먼저 들어온 순서대로 처리를 해줘야 하므로 deque이 적합.(FIFO) <br>
사실 list로 담아서 for문 처리 해도 됨
먼저 (i, j)에 이웃하는 pixel을 탐색해야 하므로 bfs, dfs가 떠오를 것이다
dfs로 구현한다고 하면
- 재귀 구현
- stack 구현
로 구현할 수 있다.
우선 재귀적으로 구현한다고 가정하고 전체적인 문제 알고리즘은 다음과 같이 생각할 수 있을 것이다.
- (i, j)의 original color를 저장한다. (original color = img[i][j])
- (i, j) 방문 처리 <- cf) img의 pixel값이 바뀌므로 고려하지 않아도 됨
- (i, j)의 pixel을 c로 바꾼다 (img[i][j]=c)
- next_x, next_y 가 img의 범위 안에 존재?
- (next_x, next_y not visited?)
- img[next_x][next_y] == original color?
- 재귀 호출
이 때 주의해야할 점은 재귀의 최대 호출횟수를 풀어줘야 한다.
sys.setrecursionlimit()
In [ ]:
from collections import deque
import sys
sys.setrecursionlimit(10**5)
def dfs(Map, nx, ny, change):
original = Map[nx][ny]
Map[nx][ny] = change
if nx+1 < H and Map[nx+1][ny] == original:
dfs(Map, nx+1, ny, change)
if nx-1 >= 0 and Map[nx-1][ny] == original:
dfs(Map, nx-1, ny, change)
if ny+1< W and Map[nx][ny+1] == original:
dfs(Map, nx, ny+1, change)
if ny-1 >= 0 and Map[nx][ny-1] == original:
dfs(Map, nx, ny-1, change)
H, W = [int(x) for x in input().split()]
img =[]
for _ in range(H):
img.append([int(x) for x in input().split()])
Q = int(input())
processing_q = deque()
for _ in range(Q):
i, j, c = [int(x) for x in input().split()]
i -= 1
j -= 1
processing_q.append((i, j, c))
while processing_q:
i, j, c = processing_q.popleft()
if img[i][j] != c:
dfs(img, i, j, c)
for i in range(H):
print(*img[i])
시간제한(stack을 이용한 dfs)¶
stack을 이용해서 dfs를 구현하는 것이 더 익숙해서 이를 이용했다가 계속 시간제한에 걸려 문제를 풀지 못했다.
참고로 dfs가 어디를 탐색하는지 알기 위해 print로 찍어보면 알고리즘이 올바르게 작동하는지 알 수 있다.
In [2]:
# 시간제한
def dfs(graph, nx, ny, c):
prev_c = graph[nx][ny]
graph[nx][ny] = c
stack=[(nx, ny)]
H, W = len(graph), len(graph[0])
move = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 북 동 남 서
while stack:
nx, ny = stack[-1]
for move_x, move_y in move:
x = nx + move_x
y = ny + move_y
print('nx: ',nx, 'ny: ', ny, 'next x: ', x, 'next y: ', y)
if x>=0 and x<H and y>=0 and y<W and graph[x][y]==prev_c:
nx, ny = x, y
stack.append((nx, ny))
graph[nx][ny] = c
break
if move_x == 0 and move_y == -1:
stack.pop()
return graph
# 입력
H, W = [int(x) for x in input().split()]
img = []
for _ in range(H):
row = input()
img.append([int(x) for x in row.split()])
# 변환
Q = int(input())
process = []
for _ in range(Q):
i, j, c = [int(x) for x in input().split()]
process.append((i, j, c))
for i, j, c in process:
img = dfs(img, i-1, j-1, c)
#출력
for row in img:
for elem in row:
print(elem, end=' ')
print()
1 9 1 1 2 2 2 1 1 2 2 2 1 5 1 1 5 2 nx: 0 ny: 4 next x: -1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 3 nx: 0 ny: 3 next x: -1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 2 nx: 0 ny: 2 next x: -1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 3 nx: 0 ny: 2 next x: 1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 1 nx: 0 ny: 3 next x: -1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 2 nx: 0 ny: 4 next x: -1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 3 nx: 0 ny: 4 next x: -1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 5 next x: -1 next y: 5 nx: 0 ny: 5 next x: 0 next y: 6 nx: 0 ny: 6 next x: -1 next y: 6 nx: 0 ny: 6 next x: 0 next y: 7 nx: 0 ny: 6 next x: 1 next y: 6 nx: 0 ny: 6 next x: 0 next y: 5 nx: 0 ny: 5 next x: -1 next y: 5 nx: 0 ny: 5 next x: 0 next y: 6 nx: 0 ny: 5 next x: 1 next y: 5 nx: 0 ny: 5 next x: 0 next y: 4 nx: 0 ny: 4 next x: -1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 3 nx: 0 ny: 3 next x: -1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 2 nx: 0 ny: 2 next x: -1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 3 nx: 0 ny: 2 next x: 1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 1 nx: 0 ny: 1 next x: -1 next y: 1 nx: 0 ny: 1 next x: 0 next y: 2 nx: 0 ny: 1 next x: 1 next y: 1 nx: 0 ny: 1 next x: 0 next y: 0 nx: 0 ny: 0 next x: -1 next y: 0 nx: 0 ny: 0 next x: 0 next y: 1 nx: 0 ny: 0 next x: 1 next y: 0 nx: 0 ny: 0 next x: 0 next y: -1 nx: 0 ny: 1 next x: -1 next y: 1 nx: 0 ny: 1 next x: 0 next y: 2 nx: 0 ny: 1 next x: 1 next y: 1 nx: 0 ny: 1 next x: 0 next y: 0 nx: 0 ny: 2 next x: -1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 3 nx: 0 ny: 2 next x: 1 next y: 2 nx: 0 ny: 2 next x: 0 next y: 1 nx: 0 ny: 3 next x: -1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: 0 next y: 2 nx: 0 ny: 4 next x: -1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: 0 next y: 3 2 2 2 2 2 2 2 2 2
위의 결과를 보면 pop을 한 후에 다시 모든 방향(동, 서, 남, 북)을 탐색하느라 시간이 많이 소비되는 것을 알 수 있다.
혹시 memoization을 이용하여 탐색의 횟수를 줄이면 시간을 줄일 수 있지 않을까 생각 했다.
이를 구현 하기 위해
- memoization = [0, 1, 2, 3]으로 초기화
- stack에 (x, y)와 더불어 memoization을 추가한다.
- len(move)만큼 반복문을 돈다. (for i in range( len(move) ):
- move_x move_y = move[i] if i in memoization
- memoization.remove(i) # i번째 탐색했으므로 제거
In [7]:
#2nd try, memoization(시간제한)
from collections import deque
def dfs(Map, nx, ny, change):
memo = [0, 1, 2, 3]
stack = [(nx, ny, memo)]
original = Map[nx][ny]
Map[nx][ny] = change
move = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 동 서 남 북
while stack:
nx, ny, memo = stack[-1]
for i in range(len(move)):
if i in memo:
move_x, move_y= move[i]
memo.remove(i)
x = nx + move_x
y = ny + move_y
print('nx: ',nx, 'ny: ', ny, 'next x: ', x, 'next y: ', y)
if x>=0 and x<H and y>=0 and y<W and Map[x][y]==original:
nx, ny = x, y
Map[nx][ny] = change
memo=[0, 1, 2, 3]
stack.append((nx, ny, memo))
print('-'*5)
break
if memo == []:
print('-'*5)
stack.pop()
break
return Map
H, W = [int(x) for x in input().split()]
img =[]
for _ in range(H):
img.append([int(x) for x in input().split()])
Q = int(input())
processing_q = deque()
for _ in range(Q):
i, j, c = [int(x) for x in input().split()]
i -= 1
j -= 1
processing_q.append((i, j, c))
while processing_q:
print('New processing\n')
i, j, c = processing_q.popleft()
img = dfs(img, i, j, c)
for i in range(H):
print(*img[i])
1 9 1 1 2 2 2 1 1 2 2 2 1 5 1 1 5 2 New processing nx: 0 ny: 4 next x: 0 next y: 5 nx: 0 ny: 4 next x: 0 next y: 3 ----- nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 0 next y: 2 ----- nx: 0 ny: 2 next x: 0 next y: 3 nx: 0 ny: 2 next x: 0 next y: 1 nx: 0 ny: 2 next x: 1 next y: 2 nx: 0 ny: 2 next x: -1 next y: 2 ----- nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: -1 next y: 3 ----- nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: -1 next y: 4 ----- New processing nx: 0 ny: 4 next x: 0 next y: 5 ----- nx: 0 ny: 5 next x: 0 next y: 6 ----- nx: 0 ny: 6 next x: 0 next y: 7 nx: 0 ny: 6 next x: 0 next y: 5 nx: 0 ny: 6 next x: 1 next y: 6 nx: 0 ny: 6 next x: -1 next y: 6 ----- nx: 0 ny: 5 next x: 0 next y: 4 nx: 0 ny: 5 next x: 1 next y: 5 nx: 0 ny: 5 next x: -1 next y: 5 ----- nx: 0 ny: 4 next x: 0 next y: 3 ----- nx: 0 ny: 3 next x: 0 next y: 4 nx: 0 ny: 3 next x: 0 next y: 2 ----- nx: 0 ny: 2 next x: 0 next y: 3 nx: 0 ny: 2 next x: 0 next y: 1 ----- nx: 0 ny: 1 next x: 0 next y: 2 nx: 0 ny: 1 next x: 0 next y: 0 ----- nx: 0 ny: 0 next x: 0 next y: 1 nx: 0 ny: 0 next x: 0 next y: -1 nx: 0 ny: 0 next x: 1 next y: 0 nx: 0 ny: 0 next x: -1 next y: 0 ----- nx: 0 ny: 1 next x: 1 next y: 1 nx: 0 ny: 1 next x: -1 next y: 1 ----- nx: 0 ny: 2 next x: 1 next y: 2 nx: 0 ny: 2 next x: -1 next y: 2 ----- nx: 0 ny: 3 next x: 1 next y: 3 nx: 0 ny: 3 next x: -1 next y: 3 ----- nx: 0 ny: 4 next x: 1 next y: 4 nx: 0 ny: 4 next x: -1 next y: 4 ----- 2 2 2 2 2 2 2 2 2
결과는 역시 시간초과
더군다나 tc결과 시간이 많이 차이나지도 않았던 걸로 기억한다.