[백준] 10026 적록색약 파이썬 풀이

안녕하세요? 닉네임간편입니다.

이번 시간에는 백준 10026 적록색약 문제를 풀어보겠습니다.

풀이는 파이썬으로 했고, Python3 기준으로 시간이 136ms가 나와 Pypy3으로는 돌리지 않았습니다.

[문제 링크]

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

10026번: 적록색약

1. 접근방식

NxN 그리드의 모든 구간을 탐색해서 영역을 구해야 하기 때문에, 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 모두 사용할 수 있습니다.
그러나 전 좀 더 직관적으로 볼 수 있고 무엇보다 제가 조금은 더 익숙한(ㅎㅎ) 너비 우선 탐색 방법을 사용했습니다.

적록색약인 사람과 그렇지 않은 사람을 구분해야 한다는 점을 제외하면, 다른 유명한 BFS 문제 중 방향키 문제와 유사한 방식으로 접근할 수 있습니다.
상하좌우로 그리드를 탐색하면서 같은 문자를 하나의 그룹으로 판단하고, 이 그룹의 개수를 반환해 답을 출력하면 되겠습니다.

2. 전체 코드

from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
paintings = [list(input().rstrip()) for _ in range(N)]
paintings_c = [[''] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if paintings[i][j] == 'G':
            paintings_c[i][j] = 'R'
        else:
            paintings_c[i][j] = paintings[i][j]
visited = [[False] * N for _ in range(N)]
visited_c = [[False] * N for _ in range(N)]
dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)


def is_valid(y, x):
    return 0 <= y < N and 0 <= x < N


def bfs(p, v, y, x):
    dq = deque()
    dq.append((y, x))
    v[y][x] = True
    ch = p[y][x]
    while dq:
        y, x = dq.popleft()
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid(ny, nx) and not v[ny][nx] and p[ny][nx] == ch:
                dq.append((ny, nx))
                v[ny][nx] = True


area = 0
c = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(paintings, visited, i, j)
            area += 1
        if not visited_c[i][j]:
            bfs(paintings_c, visited_c, i, j)
            c += 1
print(f"{area} {c}")

전체 코드는 다음과 같습니다. 이제부터 설명을 시작하겠습니다.

3. 코드 분석

1) 탐색 배열 생성 및 처리

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
paintings = [list(input().rstrip()) for _ in range(N)]
paintings_c = [[''] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if paintings[i][j] == 'G':
            paintings_c[i][j] = 'R'
        else:
            paintings_c[i][j] = paintings[i][j]
visited = [[False] * N for _ in range(N)]
visited_c = [[False] * N for _ in range(N)]

그리드 배열, 탐색 배열 생성

그리드 배열과 각 영역을 탐색했는지 여부를 확인하기 위한 탐색 배열을 두 개씩 만듭니다. 이는 적록색약인 사람과 그렇지 않은 사람을 구분하여 탐색을 진행하기 위함입니다.

그리드 배열은 paintings로, 탐색 배열은 visited로, 적록색약의 경우는 '_c'로 구분하여 생성했습니다.

이때 적록색약인 사람은 'R'과 'G'를 구분하지 못하기 때문에 적록색약인 사람의 그리드 배열에서는 'G'문자가 있다면 이를 'R'로 바꿔줍니다.

2) bfs() 함수

def bfs(p, v, y, x):
    dq = deque()
    dq.append((y, x))
    v[y][x] = True
    ch = p[y][x]
    while dq:
        y, x = dq.popleft()
        for m in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ny, nx = y + m[0], x + m[1]
            if 0 <= ny < N and 0 <= nx < N and not v[ny][nx] and p[ny][nx] == ch:
                dq.append((ny, nx))
                v[ny][nx] = True

 

a) p, v, y, x

p는 그리드 배열, v는 탐색 배열, y와 x는 좌표를 의미합니다.

적록색약인 사람과 그렇지 않은 사람의 경우를 구분해야 하기 때문에 이를 파라미터로 전달받아서 처리를 했습니다.

b) 덱, 체크 문자(ch) 생성

덱을 생성한 후 입력받은 x, y 좌표에 해당하는 문자열을 ch 변수에 저장합니다.

x,y 좌표와 인접하면서 ch 문자와 값이 같다면 같은 그룹에 속하는 것이므로, 여기서 미리 변수를 만들어줍니다.

c) 인접한 그룹 확인

덱에서 추출한 x,y 좌표에 대해 상하좌우 방향으로 탐색하여 만일 해당 좌표가 배열 범위 내에 있고, 아직 탐색하지 않았으며 그리드 배열 내에서 체크 문자(ch)와 같은 문자라면, 덱에 좌표를 넣고 탐색했음을 True로 설정합니다.

이러한 동작을 덱에 요소가 있을 때까지 반복하여 하나의 그룹이 완성되었다면 종료합니다.

3) 그룹 확인 및 출력

a = c = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(paintings, visited, i, j)
            a += 1
        if not visited_c[i][j]:
            bfs(paintings_c, visited_c, i, j)
            c += 1
print(f"{a} {c}")

 

먼저 적록색약인 사람이 봤을 때 구역의 개수를 c, 그렇지 않은 사람의 구역의 개수를 a라고 설정하겠습니다.

이루 이중 반복문을 통해 그리드 내부 전체를 탐색하면서 각 탐색 배열을 기준으로 아직 탐색하지 않은 곳이 있다면 bfs() 메서드를 통해 탐색합니다. 이후 하나의 그룹이 완성되어 bfs() 메서드가 종료되면 각 영역 별 개수를 1 추가해줍니다.

이후 값을 출력하면 끝입니다.

4. 마무리

파이썬(Python3 기준)으로 풀어본 적록색약 문제였습니다. 그래도 이제 골드 문제를 풀 수 있다는 것에 자신감을 갖고 더 열심히 공부해야겠습니다.

그럼 긴 글 봐주셔서 감사합니다.