문제 링크
https://www.acmicpc.net/problem/10026
잡담
1년전에 풀었던 문제인데, 그 때에 비해 메모리와 시간이 살짝 더 크게 나왔다.
구현
여타 DFS, BFS문제와 크게 다른 점이 없다. 다만, R과 G가 같은 색깔로 구분되어질 때의 count를 따로 생각해주어야한다.
코드
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = lambda : stdin.readline().strip()
count = dict()
blindness_count = dict()
visited = set()
def check(a, b, blindness_flag):
if blindness_flag:
blindness_set = {'R', 'G'}
if b in blindness_set:
return a in blindness_set
return a == b
def recur(x, y, n, color, graph, blindness_flag):
global visited
visited.add((x, y))
for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
new_x, new_y = x + j, y + i
if (0 <= new_x < n) and (0 <= new_y < n) and (new_x, new_y) not in visited:
if check(graph[new_y][new_x], color, blindness_flag):
recur(new_x, new_y, n, graph[new_y][new_x], graph, blindness_flag)
def dfs(n, graph, blindness_flag=False):
global visited, count, blindness_count
visited.clear()
count['R'] = 0
count['G'] = 0
count['B'] = 0
blindness_count['RG'] = 0
blindness_count['B'] = 0
for i in range(n):
for j in range(n):
if (j, i) not in visited:
if blindness_flag:
if graph[i][j] in ('R', 'G'):
blindness_count['RG'] += 1
else:
blindness_count['B'] += 1
else:
count[graph[i][j]] += 1
recur(j, i, n, graph[i][j], graph, blindness_flag)
if blindness_flag:
print(sum(blindness_count.values()))
else:
print(sum(count.values()), end=' ')
def solution() -> None:
n = int(input())
graph = []
for _ in range(n):
graph.append(list(input()))
dfs(n, graph)
dfs(n, graph, True)
if __name__ == '__main__':
solution()