새싹프로그래머의 이야기

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

문제: 그림의 색상이 주어졌을 때, 적록색약인 사람과 적록 색약이 아닌 사람이 볼 수 있는 색상의 구역 수를 각각 구하는 문제 입니다.

(이때, 적록 색약인 사람은 빨강과 초록을 구분하지 못합니다.)

풀이 방법: 그래프 탐색 방법중 BFS로 문제를 풀었습니다.

풀이 설명:

문제는 총 3가지 idea에서 착안해서 풀었습니다.

1.

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

for k in range(4):
    x = i + dx[k]
    y = j + dy[k]

위 방식을 통한, 각 위치의 상하좌우 요소 탐색. (그래프 탐색 뿐만 아니라 해당 코드를 통해 간단하게 상하좌우 요소를 접근할 수 있다는 점에서 매우 유용한 코드라고 생각합니다.)

2. BFS 를 통한 그래프 탐색

3.  색약인 경우, 파란색을 기준으로 색 판별

if color != 'B' and array[x][y] != 'B':
    visited[x][y] = True
    q.append([x,y])
elif color == 'B' and array[x][y] == 'B':
    visited[x][y] = True
    q.append([x,y])

풀이 코드:

import sys
from collections import deque

sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())

array = [[]*n for _ in range(n)]
for i in range(n):
    array[i] = list(sys.stdin.readline().strip())

cnt = 0
visited = [[False]*n for _ in range(n)]

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

def bfs(a,b,color):

    q = deque()
    q.append([a, b])
    visited[a][b] = True
    while q:
        i, j = q.pop()

        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
                continue

            if color == array[x][y]:
                visited[x][y] = True
                q.append([x,y])
    return


def bfs_blind(a,b,color):

    q = deque()
    q.append([a,b])

    visited[a][b] = True
    while q:
        i,j = q.pop()
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
                continue

            if color != 'B' and array[x][y] != 'B':
                visited[x][y] = True
                q.append([x,y])
            elif color == 'B' and array[x][y] == 'B':
                visited[x][y] = True
                q.append([x,y])
    return



for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j,array[i][j])
            cnt += 1

print(cnt,end=' ')
visited = [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs_blind(i,j,array[i][j])
            cnt += 1

print(cnt)

일단 BFS 탐색 코드를 2가지로 나누어 구현하였습니다.

적록 색맹이 아닌 경우, 탐색 시작점의 색과 동일한지 여부만 판단하면 되는 반면에

적록 색맹인 경우, 빨간색과 초록색을 동일한 색으로 보고 판단해야하기 때문입니다.

이제 BFS 함수 내부에서 상하좌우 요소를 접근하는데, 

if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
    continue

해당 코드를 통해 index가 배열을 벗어나는지를 판별함과 동시에 해당 위치를 방문한적이 있는지 판별하였습니다.

마지막으로 큐와 visited 배열을 활용하여 해당 노드를 방문한적 있는지 여부를 바탕으로 구역을 탐색하였습니다.

다른 풀이:

import sys

sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())

array = [[]*n for _ in range(n)]
for i in range(n):
    array[i] = list(sys.stdin.readline().strip())

cnt = 0
visited = [[False]*n for _ in range(n)]
def bfs(a,b,eyes,color):
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]

    for i in range(4):
        x = a + dx[i]
        y = b + dy[i]
        if x < 0 or x >= n or y < 0 or y >=n or visited[x][y]:
            continue

        if(eyes == 'color-blindness'):
            if((color != 'B') and array[x][y] != 'B'):
                visited[x][y] = True
                bfs(x, y, eyes, color)
            elif(color == 'B' and array[x][y] =='B'):
                visited[x][y] = True
                bfs(x, y, eyes, color)
            else:
                continue


        else:
            if color == array[x][y]:
                visited[x][y] = True
                bfs(x,y,eyes,color)

    return

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j,'!color-blindness',array[i][j])
            cnt += 1

print(cnt,end=' ')
visited= [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j] :
            bfs(i,j,'color-blindness',array[i][j])
            cnt += 1
print(cnt)

이 코드를 통해 문제를 맞췄지만 문제를 다시 푼 이유는 다음과 같았습니다.

1. 그래프 탐색을 반복문이 아닌 재귀로 문제를 품으로써 메모리 사용량과 속도가 반복문에 비해 떨어질 것이라고 생각했습니다.

2. 함수를 호출 할 때마다, 색약의 여부에 따라 함수를 다르게 구현한 풀이 코드와 달리 색약을 판단하는 조건문이 계속적으로 동작하기 때문에 속도가 뒤떨어질 것이라고 판단했습니다.

첫번째가 풀이 코드인데요. 반복문으로 구현한 만큼 메모리는 적게 사용했지만 오히려 속도 부분에서는 느렸습니다.

반복적인 조건문의 동작과 재귀함수의 사용으로 인해 속도 부분은 확실하게 빠를 것이라 판단했지만 그렇지 않은 결과가 나와서 조금은 당황스러웠습니다.

해당 부분을 조금 더 공부한 후, 메모리와 속도 모두 효율적인 코드를 짤 수 있기 위해 노력하려고 합니다.