[백준] 10026번 적록색약 (Python, DFS)

<문제 링크>
백준 10026번 적록색약

---

문제 요약

위 사진과 같이 R(적), G(녹), B(청)로 이루어진 NxN 입력이 주어진다.
각 색깔 별로 일정 크기만큼 모여 하나의 구역을 이루고, 상하좌우로 붙어 있으면 같은 구역이다.
-> 위 사진의 경우, R구역 2개, G구역 1개, B구역 1개 => 총 4개의 구역

여기서 적록색약은 R과 G를 구분하기 어려워 하나의 구역으로 여기게 된다. 따라서 적록색약이 나눈 구역은 다음과 같다.
-> R-G구역 2개, B구역 1개 => 총 3개의 구역

문제는 적록색약이 아닐 때 구역의 개수, 적록색약일 때 구역의 개수를 모두 출력하는 것이다.
-> 출력 : 4 3

---

문제 풀이

본 문제는 전형적인 DFS 혹은 BFS 알고리즘을 활용하는 문제이다.
(이제는 누가 내 머리에 꽂아주는 것 처럼 '보드판 + 상하좌우' 조건만 보이면 DFS/BFS가 떠오른다.)

나는 이 문제와 같이 특정 구역을 나누는 문제는 주로 DFS를 활용한다. 이번에도 역시 DFS를 활용하였다.


입력된 보드를 DFS로 탐색하는 함수 'checkArea()'를 만들었고, 이 함수는 아래와 같이 동작한다.
(색약을 영어사전에 검색해보니 ColorWeakness 라고 해서 적록색약은 'Weak', 안적록색약은 'notWeak'라고 대충 이름을 지었다.)

1. 함수 입력 : (visited 보드, 시작칸 좌표, isWeak)
2. stack을 만들고, 시작칸 좌표를 넣어둔다.
3. stack이 빈 상태가 될 때까지 while문을 돈다.
   -> stack.pop하고 해당 좌표를 현재 좌표로 둔다.
   -> 현재 좌표 기준 상하좌우를 살펴본다.
   -> 상하좌우 좌표들 중, 해당 좌표의 visited가 False인 경우에만 조건에 맞는지 판단한다.
   -> 조건에 맞으면 stack에 push하고, visited의 해당 칸도 True로 바꾼다.
   -> 반복..

여기서 stack에 push하는 조건은 'isWeak'에 따라 바뀐다.
-> isWeak == True : 적록색약, R과 G를 같은 구역으로!
-> isWeak == False : 안적록색약, 싹다 다른 구역으로!

적록색약과 안적록색약이 방문(push)하게 되는 칸은 서로 다르기 때문에 visited 리스트도 각각 만들어 주어야 한다.

'checkArea()' 함수는 각 visited 리스트를 돌며 아래와 같이 수행된다.

적록색약 visited, 안적록색약 visited를 각각 돌아다니며 False인 칸을 만나면 'checkArea()' 함수가 실행되고, 함수 내에서 하나의 구역을 모두 탐색하게 된다.

함수 한번 끝날 때마다 구역 개수를 1씩 늘려주면 정답을 구할 수 있다.

---

구현

위 내용을 토대로 아래와 같이 구현하였다.

<필자가 작성한 코드>

def checkArea(visited, pos, isWeak):
    stack = [pos]
    visited[pos[1]][pos[0]] = True

    while stack:
        curPos = stack.pop()
        for s in sameAreaCase:
            nextX = curPos[0] + s[0]
            nextY = curPos[1] + s[1]
            if nextX < 0 or nextX >= N or nextY < 0 or nextY >= N:
                continue

            visitedValue = visited[nextY][nextX]

            if not visitedValue:
                curValue = board[curPos[1]][curPos[0]]
                nextValue = board[nextY][nextX]
                if isWeak:
                    if (nextValue == curValue) or (
                        curValue == 'R' and nextValue == 'G') or (
                            curValue == 'G' and nextValue == 'R'):
                        stack.append([nextX, nextY])
                        visited[nextY][nextX] = True

                else:
                    if nextValue == curValue:
                        stack.append([nextX, nextY])
                        visited[nextY][nextX] = True


N = int(input())
board = []
for i in range(N):
    board.append(list(input()))

weakVisited = [[False] * N for i in range(N)]
notWeakVisited = [[False] * N for i in range(N)]

sameAreaCase = [[-1, 0], [1, 0], [0, -1], [0, 1]]
notWeakAns = 0
weakAns = 0

x = 0
y = 0
while x < N and y < N:
    while (y < N) and (weakVisited[y][x]):
        x += 1
        if x >= N:
            x = 0
            y += 1
    if y < N:
        weakAns += 1
        checkArea(weakVisited, [x, y], True)

x = 0
y = 0
while x < N and y < N:
    while (y < N) and (notWeakVisited[y][x]):
        x += 1
        if x >= N:
            x = 0
            y += 1
    if y < N:
        notWeakAns += 1
        checkArea(notWeakVisited, [x, y], False)

print(notWeakAns, weakAns)

본 코드의 변수 및 리스트 정보는 아래와 같다.

• board : 입력된 보드, NxN 리스트, RGB로 구성
• weakVisited : 적록색약 visited, NxN 리스트, T/F로 구성
• notWeakVisited : 안적록색약 visited
• sameAreaCase : 상하좌우, 길이 4의 리스트, (±1, 0), (0, ±1)
• weakAns : 적록색약 구역의 개수, 변수
• notWeakAns : 안적록색약 구역의 개수, 변수

코드 동작 과정은 상단에 적은 내용 그대로이다.

1. 적록색약 visited와 안적록색약 visited를 각각 돌며 False를 만나면 checkArea() 함수를 실행시키고,
2. checkArea()에서 visited를 True로 바꾸며 하나의 구역을 파악한다.
3. 결국 checkArea()가 동작한 횟수가 정답!

DFS/BFS 문제는 이제 어떻게 해결해야 하는지 대충 감이 오긴 하는데 그래도 항상 시간이 오래 걸린다ㅜ 더 많이 풀어봐야겠다..!