[Algorithm] 백준_10026번: 적록색약

오늘의 문제는 🚀 백준 10026 적록색약이다.

이제 BFS 돌리는건 자신 있는데 여러 군데서 돌리는건 어떻게 하는게 가장 최선일지 모르겠다.

이번엔 그냥 풀기만 하자라는 마음으로 이중 포문을 돌려버렸는데 통과가 되어버렸다!

테스트케이스 이해하기

적록색약을 가진 사람은 R과 G를 구분하지 못한다.

그래서 위의 입력 값을 봤을때 각각 4개의 구역, 3개의 구역 이렇게 있다고 판단한다.

알고리즘

무대뽀로 그냥 while문과 For문을 신나게 돌렸는데 통과라니? 효율성을 올릴 수 있는 방법을 추후에 고민해야겠다.

1. 적록색약일 경우와 아닐 경우을 위해 두개의 check를 만들어 준다.
2. 적록색약이 아닐 경우를 먼저 구한다.
   1. for문을 두번 돌려서 check가 아직 방문 되지 않을 경우에만 q에 append해준다.
   2. 그리고 count를 +1해줘서 구역이 늘어난 것을 체크해준다.
   3. 그럼 일단 for문을 통해서 들어온 i,j에 열결된 부분을 다 방문할때 까지 q가 돈다.
   4. 위 구조를 반복한다.
3. 이중 포문을 돌려서 “R”를 다 “G”로 바꾼다.
4. 변수가 겹치지 않게 2번을 반복해서 적록색약일 경우를 구한다.
5. 각각 구역의 수를 프린트 해준다.

정답코드

from collections import deque
n = int(input())
arr = [list(map(str, list(input()))) for _ in range(n)]
check=[[-1]*n for _ in range(n)]
check2=[[-1]*n for _ in range(n)]

dx=[0,0,-1,1]
dy=[-1,1,0,0]

#적록색약이 아닐 경우
q=deque()
count =0
for i in range(n):
    for j in range(n):
        if check[i][j] == -1:
            count += 1
            q.append((i,j))
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nxtX = x + dx[k]
                    nxtY = y + dy[k]
                    if -1 < nxtX < n and -1 < nxtY < n:
                        if check[nxtX][nxtY] == -1 and arr[x][y] == arr[nxtX][nxtY]:
                            check[nxtX][nxtY] = 1
                            q.append((nxtX, nxtY))

#R를 G로                            
for i in range(n):
    for j in range(n):
        if arr[i][j]== "R":
            arr[i][j] = "G"
            

#적록색약 일 경우            
q2=deque()
count2 =0
for i in range(n):
    for j in range(n):
        if check2[i][j] == -1:
            count2 += 1
            q2.append((i,j))
            while q2:
                x, y = q2.popleft()
                for k in range(4):
                    nxtX = x + dx[k]
                    nxtY = y + dy[k]
                    if -1 < nxtX < n and -1 < nxtY < n:
                        if check2[nxtX][nxtY] == -1 and arr[x][y] == arr[nxtX][nxtY]:
                            check2[nxtX][nxtY] = 1
                            q2.append((nxtX, nxtY))
                            

print(count,count2)

🚀Reference: 백준 10026 적록색약