10026. 적록색약

문제

코드 & 풀이

개념을 이해하기 위하여 구체적이고 순서대로 풀었음

1. 적록색약일 때, 아닐 때 두가지를 나누어서 각각 함수로 만들고
2. 둘을 합쳐보는 과정을 거쳤다

• 적록색약일 경우

def RGnB(i, j, flag):
    global cnt
    color = flag
    arr[i][j] = 0
    for k in range(4):
        ni, nj = i + dir[k][0], j + dir[k][1]
        if 0 <= ni < N and 0 <= nj < N:
            if color == 'R':
                if arr[ni][nj] == 'R' or arr[ni][nj] == 'G':
                    RGnB(ni, nj, color)
            elif color == 'G':
                if arr[ni][nj] == 'R' or arr[ni][nj] == 'G':
                    RGnB(ni, nj, color)
            else:
                if flag == arr[ni][nj]:
                    RGnB(ni, nj, color)

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] != 0:
            # RGB(i, j, arr[i][j])
            RGnB(i, j, arr[i][j])
            cnt += 1

• 적록색약이 아닐 경우

def RGB(i, j, flag):
    global cnt
    color = flag
    arr[i][j] = 0
    for k in range(4):
        ni, nj = i+dir[k][0], j+dir[k][1]
        if 0<=ni<N and 0<=nj<N and flag == arr[ni][nj]:
            RGB(ni, nj, color)

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] != 0:
            RGB(i, j, arr[i][j])
            # RGnB(i, j, arr[i][j])
            cnt += 1

이 때 아차 한 점... 방문 배열로 풀지 않고 그래프에 직접적으로 낙서를 해가면서 풀다 보니 하나를 돌면 더이상 돌 수 없다는 문제가 생김

방문배열로 다시 풀어보았음...

def RGB(i, j, flag):
    global cnt
    v1[i][j] = 1
    for k in range(4):
        ni, nj = i+dir[k][0], j+dir[k][1]
        if 0<=ni<N and 0<=nj<N and flag == arr[ni][nj] and v1[ni][nj] == 0:
            RGB(ni, nj, flag)

def RGnB(i, j, flag):
    global rcnt
    arr[i][j] = 0
    color = flag
    for k in range(4):
        ni, nj = i + dir[k][0], j + dir[k][1]
        if 0 <= ni < N and 0 <= nj < N:
            if color == 'R':
                if arr[ni][nj] == 'R' or arr[ni][nj] == 'G':
                    RGnB(ni, nj, color)
            elif color == 'G':
                if arr[ni][nj] == 'R' or arr[ni][nj] == 'G':
                    RGnB(ni, nj, color)
            else:
                if flag == arr[ni][nj]:
                    RGnB(ni, nj, color)

N = int(input())
arr = [list(input()) for _ in range(N)]
v1 = [[0]*N for _ in range(N)]

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt, rcnt = 0, 0

for i in range(N):
    for j in range(N):
        if v1[i][j] == 0:
            RGB(i, j, arr[i][j])
            cnt += 1
for i in range(N):
    for j in range(N):
        if arr[i][j]:
            RGnB(i, j, arr[i][j])
            rcnt += 1

print(cnt, rcnt)

방문배열을 두개다 써야하나 싶었지만, 한번 돌면 상관 없기때문에 적록색약이 아닐때를 먼저 돌고, 이후에 적록색약일 경우에는 원래 썼던대로 2차원 리스트에 낙서를 해가면서 풀었다

내가 푼 방식은 dfs인것 같다... 맞나요..?
오랜만에 구글검색 안해보고 풀어서 너무 뿌듯하다!!!!!!