BOJ 10026 적록색약

https://www.acmicpc.net/problem/10026
시간 1초, 메모리 128MB
input :

• N (1 ≤ N ≤ 100)
• N개 줄에는 그림이 주어진다.

output :

• 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력

조건 :

• 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
• 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

---

간단한 구역 나누는 문제이다.

적록색약일 때의 구역과, 아닐 때의 구역을 구획하는 함수를 나누어 만들고 수행하자.

적록색약일 때는 target 문자가 'R', 'G' 일 때에 둘 다를 찾아간다.

def bfs_rb(pos_x, pos_y, target):
    q = deque([])
    visit[pos_x][pos_y] = 1
    q.append((pos_x, pos_y))

    while q:
        pos_x, pos_y = q.popleft()

        for j in range(4):
            nx = pos_x + dx[j]
            ny = pos_y + dy[j]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if target == 'R' or target == 'G':
                if visit[nx][ny] == 0 and (graph[nx][ny] == 'R' or graph[nx][ny] == 'G'):
                    q.append((nx, ny))
                    visit[nx][ny] = 1
            else:
                if visit[nx][ny] == 0 and graph[nx][ny] == 'B':
                    q.append((nx, ny))
                    visit[nx][ny] = 1

적록색약일 때만 target이 'R' 이면 -> 'R', 'G' 둘 다를.
target이 'G'이면 -> 'R', 'G'를 둘 다 찾아가는 것이다.
visit 배열의 값이 중요하다. visit[nx][ny]가 0 인 경우에만 들어가기 때문에 이에대한 조건이 필요하다.

적록색약이 아닌 경우에는 target 문자열인지만 따지면 된다.

def bfs(pos_x, pos_y, target):
    q = deque([])
    visit[pos_x][pos_y] = 1
    q.append((pos_x, pos_y))

    while q:
        pos_x, pos_y = q.popleft()

        for j in range(4):
            nx = pos_x + dx[j]
            ny = pos_y + dy[j]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if visit[nx][ny] == 0 and graph[nx][ny] == target:
                q.append((nx, ny))
                visit[nx][ny] = 1

그리고 bfs에 몇 번을 들어가는지가 각 구역을 나타내는 것이다.

ans_one = 0
ans_two = 0
for i in range(2):
    visit = [[0] * n for _ in range(n)]

    for x in range(n):
        for y in range(n):
            if visit[x][y] == 0:
                if i == 0:
                    bfs(x, y, graph[x][y])
                    ans_one += 1
                else:
                    bfs_rb(x, y, graph[x][y])
                    ans_two += 1

import sys
from collections import deque

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


def bfs_rb(pos_x, pos_y, target):
    q = deque([])
    visit[pos_x][pos_y] = 1
    q.append((pos_x, pos_y))

    while q:
        pos_x, pos_y = q.popleft()

        for j in range(4):
            nx = pos_x + dx[j]
            ny = pos_y + dy[j]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if target == 'R' or target == 'G':
                if visit[nx][ny] == 0 and (graph[nx][ny] == 'R' or graph[nx][ny] == 'G'):
                    q.append((nx, ny))
                    visit[nx][ny] = 1
            else:
                if visit[nx][ny] == 0 and graph[nx][ny] == 'B':
                    q.append((nx, ny))
                    visit[nx][ny] = 1


def bfs(pos_x, pos_y, target):
    q = deque([])
    visit[pos_x][pos_y] = 1
    q.append((pos_x, pos_y))

    while q:
        pos_x, pos_y = q.popleft()

        for j in range(4):
            nx = pos_x + dx[j]
            ny = pos_y + dy[j]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if visit[nx][ny] == 0 and graph[nx][ny] == target:
                q.append((nx, ny))
                visit[nx][ny] = 1


n = int(sys.stdin.readline())
graph = []
for i in range(n):
    graph.append(list(sys.stdin.readline().strip()))


ans_one = 0
ans_two = 0
for i in range(2):
    visit = [[0] * n for _ in range(n)]

    for x in range(n):
        for y in range(n):
            if visit[x][y] == 0:
                if i == 0:
                    bfs(x, y, graph[x][y])
                    ans_one += 1
                else:
                    bfs_rb(x, y, graph[x][y])
                    ans_two += 1
print(ans_one, ans_two)