[백준] 10026번: 적록색약

문제

그래프 문제를 처음 만났을 떄는 아니 이걸 어떻게 풀어 싶었지만,
이제는 흠 일단은 DFS, BFS 기본 코드 냅다 써보자라는 생각이 든다.
거기서 매개변수나 구해야하는 데이터를 어떻게 핸들링하냐의 문제가 됐다.

아무튼 이번에 다른 스터디원분께서 가져오신 그래프 문제는 적록색약!
비슷한 문제로는 섬의 개수!

(틀린) 풀이

틀렸습니다!

import sys
input = sys.stdin.readline

gridLength = int(input())

colorMap = [[] for _ in range(gridLength)]

for i in range(gridLength):
    rowInfo = list(input().strip())
    colorMap[i] = rowInfo

dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

visited = [[0]*gridLength for _ in range(gridLength)]

def BFS(mapInfo):
    unColorBlindnessCount = 1
    colorBlindnessCount = 1
    queue = [[0, 0]]
    visited[0][0] = 1

    while queue:
        r, c = queue.pop(0)
        curColor = mapInfo[r][c]

        for i in range(4):
            newR, newC = r+dr[i], c+dc[i]

            if 0<=newR<gridLength and 0<=newC<gridLength and visited[newR][newC] == 0:
                
                nextColor = mapInfo[newR][newC]

                if mapInfo[newR][newC] == curColor:
                    pass
                else:
                    unColorBlindnessCount += 1
                    if sorted([curColor, nextColor]) == ['G', 'R']:
                        pass
                    else:
                        colorBlindnessCount += 1
                visited[newR][newC] = 1

                queue.append([newR, newC])
    return unColorBlindnessCount, colorBlindnessCount

unCBCount, CBCount = BFS(colorMap)

print(unCBCount, CBCount)

딱 봐도 가독성이 떨어지면서 어딘가 틀린 곳이 나올 법한 코드이다.
그런데 이건 반례를 하나씩 찾아가면서 틀린 부분에 대한 조건문을 새로 생성하는 바람에 더러워졌다.

어차피 틀린 코드니 자세한 코드 설명은 생략하겠다.

풀이

33752KB 96ms

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

gridLength = int(input())

colorMap = [[] for _ in range(gridLength)]

for i in range(gridLength):
    rowInfo = list(input().strip())
    colorMap[i] = rowInfo

dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

def DFS(r, c):
    visited[r][c] = 1
    curColor = colorMap[r][c]
    for i in range(4):
        newR, newC = r+dr[i], c+dc[i]
        if 0<=newR<gridLength and 0<=newC<gridLength and visited[newR][newC] ==0:
            nextColor = colorMap[newR][newC]
            if nextColor == curColor:
                DFS(newR, newC)

def countRegion():
    count = 0
    for i in range(gridLength):
        for j in range(gridLength):
            if (visited[i][j]==0):
                DFS(i, j)
                count +=1
    return count

def makeColorBlind():
    for i in range(gridLength):
        for j in range(gridLength):
            if colorMap[i][j] == 'G':
                colorMap[i][j] = 'R'

visited = [[0]*gridLength for _ in range(gridLength)]
unCBCount = countRegion()

makeColorBlind()

visited = [[0]*gridLength for _ in range(gridLength)]
CBCount = countRegion()

print(unCBCount, CBCount)

colorMap은 다음과 같은 2차원 배열을 담는다.

[
	['R', 'R', 'R', 'B', 'B'], 
	['G', 'G', 'B', 'B', 'B'], 
	['B', 'B', 'B', 'R', 'R'], 
	['B', 'B', 'R', 'R', 'R'], 
	['R', 'R', 'R', 'R', 'R']
]

위에서 BFS로 했는데 값이 자꾸 틀려서 혹시 섬을 분리하는 데에 DFS로 하면 될까 싶어서 방식을 바꾸게 됐다.

근데 추후 스터디를 하고 보니 BFS, DFS 문제는 아니고 변수 처리하는 것이 달라 틀리게 된 것이었다.

BFS로 다시 한 번 풀어봐야겠다.

<기본 로직 순서>

1. (0, 0)부터 적록색약이 아닌 경우에 대한 DFS 탐색을 시작한다.
2. DFS에서 현재 포인트와 다음 탐색 포인트의 색이 같은 경우 탐색을 진행한다.
   색이 다른 경우, 탐색을 중지한다.
   탐색한 포인트들은 전부 visited에 넣어준다.
3. 이중 for문을 전부 돌면서 visited에 들어가지 않은 곳에 대해 DFS 탐색을 계속해서 진행한다.
   DFS가 중지될 때마다 구분되는 지역 수(count)에다가 +1을 해준다.
4. 적록색약이 아닌 경우 탐색이 끝나면, 이중 for문을 돌며 'G'를 전부 'R'로 바꿔준다
5. 1-2-3을 반복한다.

처음에는 최대한 for문을 적게 돌려고 한 번 돌 때 비적록색약의 경우와 적록색약의 경우 구역의 수를 세는 변수를 같이 갖고 갔는데, 이 시도가 아마 틀린 방식인 듯하다. 같이 들고 가니 조건문 처리도 까다롭고, 2차원 배열 관리도 제대로 동작하지 않는다.

따라서 비록 시간이 오래 걸릴 것 같더라도 [한 번 검사하기 -> 색 바꿔주기 -> 한 번 더 검사하기] 식으로 가니 쉽게 풀렸다.

처음부터 시간복잡도를 걱정해 그럴 듯한 풀이를 생각하기 보다는 직관적으로 생각난 풀이를 먼저 구현해보자!