본문 바로가기
알고리즘

적록색약 10026 -DFS

by 토니짱 2022. 9. 18.
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def dfs(x,y):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  visit[x][y]=True
  for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<n and 0<=ny<n and graph[x][y]==graph[nx][ny] and not visit[nx][ny]:
        dfs(nx,ny)

n=int(input())
graph = [list(map(str,input())) for _ in range(n)]
visit = [[False]*n for _ in range(n)]
cnt1 = 0
cnt2 = 0
for i in range(n):
  for j in range(n):
    if not visit[i][j] :
      cnt1+=1
      dfs(i,j)

visit = [[False]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    if graph[i][j] == 'R' :
      graph[i][j] = 'G'

for i in range(n):
  for j in range(n):
    if not visit[i][j] :
      cnt2+=1
      dfs(i,j)
      
print(cnt1)
print(cnt2)
반응형

'알고리즘' 카테고리의 다른 글

이분검색  (3) 2022.09.22
연구소 14502 BFS  (1) 2022.09.18
아기상어 16236 BFS  (1) 2022.09.18
안전영역 -2468 (DFS)  (1) 2022.09.18
설탕 배달-2839 (while-else문)  (0) 2022.09.16