https://www.acmicpc.net/problem/10026
똑같은 그림을 적록색약인 사람과, 그렇지 않은 사람이 보았을 때 영역의 개수를 구하는 문제다.
" 상하좌우를 체크해서 그래프로 연결하고, 영역의 개수를 구하면 되는거 아닌가? 쉽네~"
이렇게 생각하고 문제를 풀었다가 메모리 초과, 시간 초과, 런타임 에러를 수집했다. 🙃
처음 내 접근 방식은 아래와 같았다.
색맹 여부에 따라 그래프를 3차원 배열(...)로 만들자
➣ graph[x][y][색맹여부]
➣ 메모리초과
색맹 여부에 따라 그래프를 따로 만들자
➣ two_color_graph, three_color_graph
➣ 메모리초과
고민을 하다가 그래프를 따로 구현하지 않고, 함께 쓸 수 있는 방법을 생각해냈다.
이렇게 간단한 방법이 있는데, 몇시간동안 머리를 끙끙 싸맸다. 으으
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input().rstrip())
matrix = [list(input().rstrip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
three_cnt, two_cnt = 0, 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
#현재 색상 좌표를 방문해준다.
visited[x][y] = True
current_color = matrix[x][y]
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if (0 <= nx < n) and (0 <= ny < n):
#현재 좌표의 색상과 상하좌우 좌표에 있는 색상이 같으면 dfs로 넣어준다.
if visited[nx][ny]==False:
if matrix[nx][ny] == current_color:
dfs(nx,ny)
for i in range(n):
for j in range(n):
# 방문하지 않은 좌표이면 dfs로 넣어준다.
if visited[i][j]==False:
dfs(i,j)
three_cnt += 1
#R을 G로 바꾸어준다. --> 적록색약은 같은 색으로 보기 때문에
for i in range(n):
for j in range(n):
if matrix[i][j]=='R':
matrix[i][j]='G'
visited = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if visited[i][j] == False:
dfs(i,j)
two_cnt += 1
print(three_cnt,two_cnt)