[Python] 21938번 영상처리

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

21938번: 영상처리

---

 

22/09/13

 

 

오랜만에 풀어보는 그래프 탐색 문제여서 조금 맞왜틀을 많이 했던 문제이다.

 

지금 다시 보니 실수했던 부분이 많이 보인다.

 

이 문제를 2가지 방법으로 풀려고 해봤으나, BFS는 익숙하지 않아서 BFS로 해결하지 않았다.

---

 

문제 접근 방식:

 

 

DFS로 접근하였다. 오랜만에 DFS코드를 짜는 것이어서 많이 틀리기도 하고 시간 초과, 메모리 초과가 나기도 했다.

 

모두 그래프 자체를 변형을 시킴으로써 방문처리하는 배열 없이 그래프 내에서 방문처리를 하도록 설정하였다.

 

접근 방법 자체가 틀린 것은 아니였지만, 의문사하는 경우가 많았기에 틀린 예시 코드를 올려보고자 한다.

 

맨 처음 접근 했던 방식은 주어진 RGB 세 개의 값의 평균을 배열에다 저장함으로써 graph를 설정해주었다.

 

방문처리는 그래프의 값을 1000으로 설정하는 것으로 방문처리를 진행했으며, 1000으로 설정한 이유는 RGB의 평균이 기껏해야 255밖에 되지 않기 때문에 도달할 수 없는 값이기 때문이었다.

 

그랬더니 메모리 초과가 났으며,  그 이유는 방문처리를 한 곳을 다시 또 지나도록 코드를 잘못 설계했었기 때문이었다.

 

그러면 재귀 코드 특성상 무한루프에 빠지기 쉽다.

---

아래는 내가 위의 접근 방식과 같이 작성한 메모리 초과 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21938번 영상처리
# 그래프 이론, 그래프 탐색, DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N, M = map(int, input().rstrip().split())
graph = []
count = 0  # 연결 요소의 개수를 세는 변수
for _ in range(N):
    line = list(map(int, input().rstrip().split()))
    row = []
    for i in range(M):
        k = line[3*i] + line[3*i+1] + line[3*i+2]
        row.append(k / 3)
    graph.append(row)
T = int(input())

def dfs(row, col, T):
    global count
    if row >= N or row < 0 or col >= M or col < 0:
        return
    elif graph[row][col] < T:
        return
    else:
        graph[row][col] = 1000
        dfs(row+1, col, T)
        dfs(row-1, col, T)
        dfs(row, col+1, T)
        dfs(row, col-1, T)
        count += 1
        return

for row in range(N):
    for col in range(M):
        dfs(row, col, T)

print(count)

 

---

 

두 번째로 접근했던 코드는 마지막에서 for문을 통해 dfs를 돌리는 부분에서 graph[row][col]의 값이 T보다 클 때만 돌게 했었는데, 결국은 방문 처리한 곳을 다시 또 돌게 만드는 행위였으므로 의미 없는 행위였다.

 

이때는 메모리 제한이 문제인 줄 알고 재귀 깊이를 줄였으나, 무한루프에 빠지는 것 자체가 문제였기 때문에 recursion error가 나왔다.

 

세 번째로 접근했던 코드는 방문처리를 1000이 아니라 0으로 바꾸는 작업을 했다.

그러면 다행히 일반적인 경우에선 dfs를 진행할 때 elif 부분에서 방문을 한 곳은 걸러지기 때문에 괜찮아진다.

하지만 이래도 문제가 생기는데, 평균값이 애초에 0인 곳은 방문처리를 하지 않은 것과 별반 차이가 없다는 점이 문제였다.

 

그래서 -1로 바꿔줘서 4번째 제출을 진행했는데 이번엔 연결 요소를 구하는 방식 자체가 문제라는 점을 깨달아버렸다.

for문으로 dfs를 진행하는데 dfs진행이 끝나면 count변수를 +1 하는 방식으로 연결 요소의 개수를 구하도록 했는데, 그러면 dfs를 돌릴 때마다 그냥 count변수가 늘어나므로 문제가 생겨버린다.

 

그래서 마지막으로, 그냥 dfs를 진행할 때 count변수를 안에서 늘리는 것보다 return을 해줌으로써 바깥에서 늘려주는 형식으로 해야겠다고 생각했다.

또한, 너무 많이 틀려서 구현 방식 자체를 문제에서 주는 것처럼 그대로 진행하기로 했다.

RGB를 평균 내준 다음 그 값이 T보다 클 때는 1 아니면 0으로 바꿔 graph에 저장하기로 했다.

이후 맞았습니다를 받았다.

 

틀린 코드들이 궁금하다면 위의 문제에서 내 아이디 lighter로 검색하면 공개 코드로 나와있으니 살펴보면 될 것이다.

---

아래는 내가 마지막의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21938번 영상처리
# 그래프 이론, 그래프 탐색, BFS
import sys
input = sys.stdin.readline
from math import ceil
sys.setrecursionlimit(500000)

N, M = map(int, input().rstrip().split())
graph = []
count = 0  # 연결 요소의 개수를 세는 변수
for _ in range(N):
    line = list(map(int, input().rstrip().split()))
    row = []
    for i in range(M):
        k = line[3*i] + line[3*i+1] + line[3*i+2]
        row.append(k/3)
    graph.append(row)
T = int(input())

for row in range(N):
    for col in range(M):
        if graph[row][col] >= T:
            graph[row][col] = 1
        else:
            graph[row][col] = 0

def dfs(row, col):
    if 0 <= row < N and 0 <= col < M and graph[row][col] == 1:
        graph[row][col] = 0
        dfs(row+1, col)
        dfs(row-1, col)
        dfs(row, col+1)
        dfs(row, col-1)
        return 1

for row in range(N):
    for col in range(M):
        if bool(graph[row][col]):
            count += dfs(row, col)

print(count)

# 21938번 영상처리
# 그래프 이론, 그래프 탐색, BFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

N, M = map(int, input().rstrip().split())
graph = []
count = 0  # 연결 요소의 개수를 세는 변수
for _ in range(N):
    line = list(map(int, input().rstrip().split()))
    row = []
    for i in range(M):
        k = line[3*i] + line[3*i+1] + line[3*i+2]
        row.append(k/3)
    graph.append(row)
T = int(input())

def dfs(row, col, T):
    global count
    if row >= N or row < 0 or col >= M or col < 0:
        return 0
    elif graph[row][col] < T:
        return 0
    else:
        graph[row][col] = -1
        dfs(row+1, col, T)
        dfs(row-1, col, T)
        dfs(row, col+1, T)
        dfs(row, col-1, T)
        return 1
    return 0

for row in range(N):
    for col in range(M):
        if graph[row][col] >= T:
            count += dfs(row, col, T)

print(count)