BOJ 10026번 : 적록 색약 (Python/Gold 5)

10026번: 적록색약

---

설명

위의 그림과 같이 크기가 5x5인 그리드가 주어졌다고 하자. R은 빨간색, B는 파란색, G는 초록색을 나타낸 것이다. 같은 색끼리 인접해 있으면 그건 하나의 구역이다. 이 문제는 적록색약이 아닌 경우와 적록색약인 경우로 나눠서 구하는 문제이다. 적록색약인 경우는 빨간색과 초록색을 구분하지 못해서 같은 색으로 보일 것이다. 따라서 두 경우를 나눠서 구역을 구해보자. 아래는 구역을 색깔별로 구분해서 구역을 나타낸 것이다.

그리드 안에 검은색 선은 구역을 나눈 것을 나타낸 것이다. 적록색약이 아닌 경우를 보면 구역이 총 4개(빨2, 초1, 파1)로나눠진 것을 볼 수 있다. 그러나 적록색약인 경우는 빨간색과 초록색이 구분이 없어져서 구역이 총 3개(빨2, 파1)로 나눠진 것을 볼 수 있다. (필자는 초록색을 빨간색으로 칠했다.) 

 

풀이

✔ BFS/DFS 알고리즘 이용

1. 파이썬에서 BFS/DFS를 구현하기 위해서는 큐/스택이 필요하다. 큐와 스택을 모두 사용할 수 있는 덱을 가져온다.

from collections import deque
import sys
input = sys.stdin.readline #입출력 향상

2. 그리드를 탐색할 때 지나갈 수 있는지 확인하기 위한 변수 dx, dy 생성

알고리즘을 구현하기 전에 필요한 변수가 있다. (함수 내에서 해도 되지만 편의상 먼저 정의)

만약 3x3 미로(좌측 그림)가 있다고 가정하자. (0, 0)에서 지나갈 수 있는 길인지 확인하기 위해서는 현재위치에서 주변을 다 확인해봐야 하는데, 문제에서 인접한 칸으로만 이동할 수 있다고 했으므로 대각선을 제외한 상하좌우만 확인해보면 된다.

확인하는 방법은 현재 위치에서 다른 위치로 이동하면서 해야 한다. 상하좌우 4개의 데이터만 필요하므로 x, y 변수에 각 네 개의 값만 넣는다. 맨 우측의 그림을 보면 좌표로 나타낸 것을 볼 수 있는데, 이는 현재 위치에서 한 칸을 이동했을 때의 좌표를 나타낸 것이다. 그럼 dx에 x좌표만 저장하면 되므로 [(좌)-1, (우)1, (상)0, (하)0], 그리고 dy에는 y좌표인 [(좌)0, (우)0, (상)1 (하)-1] 이렇게 저장한다. 필자는 좌우하상 순대로 저장했지만, 본인이 편한 순서대로 저장하면 된다. (단 x와 y 모두 순서에 맞게 저장해야 한다. 즉, x는 좌우하상인데 y는 좌우상하 이런식으로 저장하면 안 된다는 것이다.)

이건 앞으로 그래프 탐색할 때 필수로 있어야 하므로 기억해두자.

#상하좌우를 다 확인하기 위한 걸 추가 (아래는 좌우상하 순대로 저장)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

 

3. BFS 혹은 DFS 알고리즘을 정의한다.

 

3.1 BFS

def BFS(x, y):
    q = deque() #큐 생성
    q.append((x, y)) #큐에 초기 위치 넣기
    visited[x][y] = 1 #방문 표시

파이썬에서는 함수를 정의하려면 def를 쓰면 된다. BFS 함수 인수에 좌표값(0, 0)을 넣어야 하므로 x와 y를 쓴다. 다음으로는 큐를 사용하기 위해 덱을 생성한다. 덱의 이름은 q라고 정의했고, 초기 위치를 q에 넣는다. 그리고 뒤에서 자세히 살펴볼 거지만, 구역의 개수를 카운트할 때 방문 안 했을 때 BFS 문을 돌리고 그때마다 카운트를 하기 때문에 방문했다는 표시가 필요하다. 

while q:
        x, y = q.popleft()  # 꺼내기

        # 좌표 이동하면서 상하좌우 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

이제  좌표를 이동시키면서  같은 구역에 있는 걸 찾는다. popleft()는 덱의 가장 왼쪽에 있는 걸 빼내고 삭제한다. 덱에 있는 현재 좌표를 꺼내서 x, y에 저장한다. 다음으로는 현재 좌표에서 상하좌우를 확인한다. 

            if -1 < nx < N and -1 < ny < N: 
                if graph[nx][ny] == graph[x][y] and visited[nx][ny] == 0:
                    visited[nx][ny] = 1  #방문체크 후 큐에 넣음
                    q.append((nx, ny))

그러나 이동한 좌표가 그리드 밖으로 벗어날 수도 있다. 위의 그림(2번)에서 현재 좌표가 (0, 0) 일 때 상하좌우를 확인하면 X표시 된 것을 볼 수 있는데 그건 미로 밖에 있기 때문에 값이 없다고 표시한 것이다. 따라서 그리드 내에서만 움직일 수 있도록 조건문을 넣어줬다.

다음으로는 상하좌우를 확인하다가 이동한 위치가 이동하기 전 위치와 글자와 같다면 방문 표시를 한다. 만약 현재 좌표가 (0, 0)일 때 graph[0][0]이고 이 값은 현재 'R'이다. 거기서 우측(graph[0][1])으로 한 칸 이동했더니 'R'이 있다. 이런식으로 같은 구역인지 아닌지를 찾아내는 것이다.

그리고 이동된 좌표를 다시 큐에 넣는다. 그럼 이동된 좌표가 현재 위치가 된다. 상하좌우를 다 확인했으면 다시 큐에서 현재 위치를 꺼내서 큐가 빌 때까지 과정을 반복한다.

 

3.2 DFS 

DFS를 정의하기 전에 해줘야 하는 게 있다.

import sys
sys.setrecursionlimit(100000)

파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이기 때문에 'sys.setrecursionlimit(100000)' 이 코드를 넣어주지 않으면 런타임 에러가 발생할 수 있다. 따라서 DFS를 사용할 때에 기본적으로 추가해주자.

def DFS(x, y):
    visited[y][x] == 1

    #좌우상하 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx <= N and 0 <= ny <= N and visited[ny][nx] == 0 and graph[ny][nx] == graph[y][x]:
            DFS(nx, ny)

DFS도 거의 비슷하지만 BFS보다 풀이가 간단한 걸 볼 수 있다. 먼저 현재 좌표의 방문표시를 해준다. 그런데 DFS와 다르게 x와 y의 위치가 바뀌었다. 이유는 넓이 탐색이 아니라 깊이 탐색이기 때문에 아래쪽으로 탐색하기 위해서이다.

좌우상하를 확인하면서 그리드 범위를 벗어나지 않고 이전 위치와 현재 위치의 색깔이 같을 때 방문하지 않았으면 재귀를 돌린다. 

 

4. Main (입력 부분)

N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(str, input().rstrip())))
#graph = [list(map(str, input().rstrip())) for _ in range(N)] 이렇게도 가능하다.

그리드의 크기와 그리드를 나타낸 것이다. 

 

5. 적록색약이 아닌 경우와 적록색약인 경우를 나눔

#적록색약이 아닌 경우
visited = [[0]*N for _ in range(N)] #방문 표시
cnt1 = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt1 += 1
            BFS(i, j) #DFS(j, i) 

#적록색약인 경우
#visited = [[0 for _ in range(N)] for _ in range(N)] 이렇게도 가능
visited = [[0]*N for _ in range(N)] #초기화
cnt2 = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G': #G -> R로 변환
            graph[i][j] = 'R'

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt2 += 1
            BFS(i, j) #DFS(j, i) 
print(cnt1, cnt2)

먼저 이중for문으로 방문하지 않은 것(0)을 카운트 해주고 BFS를 돌린다. 이렇게 하면 BFS가 돌아가면서 방문 표시를 해주고 BFS가 끝났으면 다시 for문으로 돌아와서 방문하지 않은 곳을 탐색한다. 이렇게 해서 구역을 나눠주는 것이다.

적록색약일 경우에 방문 리스트를 다시 초기화해주고 빨간색과 초록색 중 하나를 같은 색으로 바꿔준다. 필자는 초록색을 빨간색으로 바꿔줬다. 그리고 아까처럼 반복해준다. 주의할 것은 DFS함수를 호출할 때는 i와 j의 위치를 바꿔줘야 한다.

마지막으로 구역을 출력한다.

 

BFS 풀이 (전체 코드)

from collections import deque
import sys
input = sys.stdin.readline #입출력 향상

N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(str, input().rstrip())))

def BFS(x, y):
    # 좌우상하
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    q = deque() #큐 생성
    q.append((x, y)) #큐에 초기 위치 넣기
    visited[x][y] = 1

    #좌표 이동하면서 확인
    while q:
        x, y = q.popleft() #큐에서 꺼내서 x, y에 넣기

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

            if -1 < nx < N and -1 < ny < N: #이게 문제
                if graph[nx][ny] == graph[x][y] and visited[nx][ny] == 0:
                    visited[nx][ny] = 1  # 방문체크 후 큐에 넣음
                    q.append((nx, ny))

#적록색약이 아닌 경우
visited = [[0 for _ in range(N)] for _ in range(N)] #방문 표시
cnt1 = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            BFS(i, j)
            cnt1 += 1

#적록색약인 경우
visited = [[0 for _ in range(N)] for _ in range(N)]
cnt2 = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G': #G -> R로 변환
            graph[i][j] = 'R'

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            BFS(i, j)
            cnt2 += 1
print(cnt1, cnt2)

 

DFS 풀이 (전체 코드)

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def DFS(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[y][x] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and graph[y][x] == graph[ny][nx] and visited[ny][nx]==0:
            DFS(nx, ny)

N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(str, input().rstrip())))
visited = [[0]*N for _ in range(N)] #방문 표시
cnt1 = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt1 += 1
            DFS(j, i)

#적록색약
visited = [[0]*N for _ in range(N)]
cnt2 = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G': #G -> R로 변환
            graph[i][j] = 'R'

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            cnt2 += 1
            DFS(j, i)
print(cnt1, cnt2)