적록색약 - BOJ

적록색약 - BOJ

from collections import deque
from copy import deepcopy

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def a_bfs(i, j):
    cnt = 0
    q1 = deque()
    q1.append((i, j))
    a_visit[i][j] = True
    while q1:
        x, y = q1.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N  or ny >= N or a_visit[nx][ny]:
                continue
            if a[nx][ny] == a[i][j]:
                a_visit[nx][ny] = True
                q1.append((nx, ny))


def b_bfs(i, j):
    cnt = 0
    q2 = deque()
    q2.append((i, j))
    b_visit[i][j] = True
    while q2:
        x, y = q2.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or b_visit[nx][ny]:
                continue
            if b[nx][ny] == b[i][j]:
                b_visit[nx][ny] = True
                q2.append((nx, ny))


N = int(input())
a = [list(input()) for _ in range(N)]
b = deepcopy(a)
for i in range(N):
    for j in range(N):
        if b[i][j] == 'G':
            b[i][j] = 'R'

a_visit = [[False] * N for _ in range(N)]
b_visit = [[False] * N for _ in range(N)]

a_cnt = 0
b_cnt = 0

for i in range(N):
    for j in range(N):
        if not a_visit[i][j]:
            a_bfs(i, j)
            a_cnt += 1
        if not b_visit[i][j]:
            b_bfs(i, j)
            b_cnt += 1

print(a_cnt, b_cnt)

https://nuatmochoi.github.io/algopress/

위 주소의 깃 블로그에 알고리즘 풀이 작성하고 있습니다!

1. 예증법 : 특정한 사례들을 나열한 뒤 그 안에서 일반적인 규칙을 찾는다.

2. 패턴 매칭 : 풀어야 할 알고리즘과 비슷한 문제를 생각해내고 비슷한 문제의 풀이법을 수정하여 풀어야 할 알고리즘을 만들어낸다.

3. 단순화와 일반화 : 문제를 단순화하여 푼 뒤, 알고리즘이 구해지면 일반화

4. 초기 사례로부터의 확장 : n=1, n=2, n=3,... 식으로 확장하여 규칙을 찾아낸다. 보통 재귀 알고리즘으로 구현된다.

5. 자료구조 브레인스토밍 : 자료구조들을 차례차례 적용해보고 해결되는지 본다.