10026 - 적록색약

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

10026번: 적록색약

 

- 그래프 탐색

 

import sys
sys.setrecursionlimit(int(1e9))

input = sys.stdin.readline

def dfs(r, c):
    v = data[r][c]
    data[r][c] = 'N'

    for i, j in delta:
        dr = r + i
        dc = c + j

        if 0 <= dr < n and 0 <= dc < n and v == data[dr][dc]:
            dfs(dr, dc)

def dfs2(r, c):
    v = data2[r][c]
    data2[r][c] = 'N'

    for i, j in delta:
        dr = r + i
        dc = c + j

        if 0 <= dr < n and 0 <= dc < n and v == data2[dr][dc]:
            dfs2(dr, dc)   


n = int(input())
data = [list(input().rstrip()) for _ in range(n)]

data2 = list()
for i in range(n):
    arr = list()
    for j in range(n):
        if data[i][j] == 'G':
            arr.append('R')
        else:
            arr.append(data[i][j])
    data2.append(arr)

delta = [[1,0],[-1,0],[0,1],[0,-1]]
cnt, cnt2 = 0, 0
for i in range(n):
    for j in range(n):
        if data[i][j] != 'N':
            dfs(i, j)
            cnt += 1
        if data2[i][j] != 'N':
            dfs2(i, j)
            cnt2 += 1

print(cnt, cnt2)

 

DFS로 구현했다

그냥 DFS 할 때마다 한 번씩 카운팅해주면 되는 문제

두 번만 하면 됨