230219 [10026: DFS]

사방면에 같은 색깔 있는지 검사 DFS

그냥 DFS

‘R’을 ‘G’로 바꾸고 DFS 한번 더

 

import sys
from collections import deque
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def DFS(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[y][x] = 1

    for i in range(4):
        nowx, nowy = x+dx[i], y+dy[i]
        if 0<=nowx<N and 0<=nowy<N and graph[y][x] == graph[nowy][nowx] and visited[nowy][nowx] == 0:
            DFS(nowx, nowy)

N = int(input().rstrip())
graph = [list(input().rstrip()) for _ in range(N)]
visited = [[0] * (N) for _ in range(N)]

cnt1 = 0

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt1 += 1
            DFS(j, i)

for i in range(N):
    for j in range(N):
        if graph[i][j] == 'R':
            graph[i][j] = 'G'

cnt2 = 0
visited = [[0] * (N) for _ in range(N)]

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt2+=1
            DFS(j, i)

print(cnt1, cnt2)