[Python] 백준 10026 적록색약 - BFS

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

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

---

풀이

• BFS 이용(DFS도 사용 가능)
• 색약이 있는 사람들은 R, G를 모두 똑같은 색으로 인식한다. -> 'G'을 'R'로 변경('R' -> 'G'도 가능)
• BFS 함수에서 상하좌우의 값을 확인하고 동일하면 큐에 집어 넣는다. 그래프의 모든 값을 확인하고 영역의 수를 구해야하는 문제이기 때문에 상하좌우의 값이 현재 큐에서 꺼낸 좌표에 들어있는 값과 같다면 큐에 넣은 후 다시 주변을 탐색한다.

!! 처음에는 BFS 함수의 매개변수로 색깔값을 받아왔는데, 이는 모든 값을 확인해줘야 하기 때문에 코드가 지저분하고 반복적인 부분이 많았다. 코드를 계속 치면서도 내가 조금 이상하고 복잡하게 풀고 있다는 느낌을 받았었는데 역시나 잘못된 방법이었다.

수정 전

def Bfs(x, y, color):
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if board[nx][ny] == color and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

수정 후

def Bfs(x, y):
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if board[nx][ny] == board[x][y] and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

• 위 코드를 이용하면 메인 코드에서 방문 여부만 판단하여 그래프를 탐색할 수 있다.
• 색약의 유무에 따라 영역의 수를 출력 -> BFS 2번 사용해야 하며 이때 방문 그래프와 영역의 수를 초기화한 뒤 BFS를 실행해야 한다.

코드

from collections import deque;

# 상하좌우 방향벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 영역의 수
cnt = 0

def Bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            # 현재 값과 상하좌우 값 비교하여 같으면 큐에 집어 넣고 방문 처리를 해주는 부분
            if board[nx][ny] == board[x][y] and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

if __name__ == "__main__":
    N = int(input())
    board = [list(input().strip()) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]

    # 적록색약이 아닐 때
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                Bfs(i, j)
                cnt += 1
    
    # 줄바꿈X 공백 구분 위해 end=' ' 사용
    print(cnt, end=' ')

    # 적록색약일 때: G를 R로 변경해준 뒤 탐색
    for i in range(N):
        for j in range(N):
            if board[i][j] == 'G':
                board[i][j] = 'R'

    # 방문 배열, 영역의 수 초기화
    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)
                cnt += 1

    print(cnt)